Ragil VR|46: Lintasan Terpendek dengan Algoritma Dijkstra

Lintasan Terpendek (Shortest Path)

Lintasan terpendek merupakan lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan yang dimaksud tersebut dapat dicari dengan menggunakan graf.

Persoalan dalam mencari lintasan terpendek ini sering terjadi dalam kehidupan sehari hari. Graft yang digunakan dalam pencarian lintasan terpendek adalah graft berbobot (weight graph), yaitu graft yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graft dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya.asumsi yang digunakan adalah bahwa semua bobot bernilai positif. Kata “terpendek” berarti meminimisasi bobot pada suatu lintasan di dalam graft.

Hingga saat ini, sudah banyak algoritma mencari lintasan terpendek yang pernah ditulis. Akan tetapi algoritma lintasan terpendek yang paling terkenal adalah algoritma dijkstra. Algoritma dijkstra pertama kali dikembangkan oleh E.W.Dijkstra yaitu seorang ilmuan computer berkebangsaan belanda yang pada perkembangannya menggunakan struktur data yang berbeda-beda, serta memakai strategi greedy, dimana pada setiap langkah dipilih sisi-sisi dengan bobot terkecil yang menghubungkan setiap simpul yang sudah terpilih dengan simpul lainnya.

Terdapat beberapa jenis persoalan lintasan terpendek, anatara lain:

1. Lintasan terpendek antara dua simpul tertentu.

2. Lintasan terpendek antara semua pasangan simpul.

3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.

4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.

Dibawah ini merupakan contoh program membuat lintasan terpendek menggunakan bahasa pemprograman c++.

#include<stdio.h>

#include<conio.h>

#include<process.h>

#include<string.h>

#include<math.h>

#define IN 99

#define N 6

int dijkstra(int cost[][N], int source, int target);

int dijsktra(int cost[][N],int source,int target)

{

int dist[N],prev[N],selected[N]={0},i,m,min,start,d,j;

char path[N];

for(i=1;i< N;i++)

{

dist[i] = IN;

prev[i] = -1;

}

start = source;

selected[start]=1;

dist[start] = 0;

while(selected[target] ==0)

{

min = IN;

m = 0;

for(i=1;i< N;i++)

{

d = dist[start] +cost[start][i];

if(d< dist[i]&&selected[i]==0)

{

dist[i] = d;

prev[i] = start;

}

if(min>dist[i] && selected[i]==0)

{

min = dist[i];

m = i;

}

start = m;

selected[start] = 1;

}

start = target;

j = 0;

while(start != -1)

{

path[j++] = start+65;

start = prev[start];

}

path[j]='\0';

strrev(path);

printf("%s", path);

return dist[target];

}

int main()

{

int cost[N][N],i,j,w,ch,co;

int source, target,x,y;

printf("\t****Lintaan Algoritma Terpendek (DIJKSRTRA's ALGORITHM)****\n\n");

for(i=1;i< N;i++)

for(j=1;j< N;j++)

cost[i][j] = IN;

for(x=1;x< N;x++)

{

for(y=x+1;y< N;y++)

{

printf(" Masukkan nilai dari jalur antara simpul %d dan %d: ",x,y);

scanf("%d",&w);

cost [x][y] = cost[y][x] = w;

}

printf("\n");

}

printf("\n Masukkan asal simpul: ");

scanf("%d", &source);

printf("\n Masukkan target simpul: ");

scanf("%d", &target);

co = dijsktra(cost,source,target);

printf("\n Jalur Terpendek: %d",co);

getch();

return(0);

}

Algoritma program diatas adalah sebagai berikut:

Pada program diatas memiliki dua blok program yaitu terdari blok int dijkstra(int cost[][N], int source, int target);. Blok ini digunakan untuk membuat jalur graf yang nantinya akan dihubungkan oleh jalan yang mempunyai jarak yang bernilai tertentu. Yang kedua adalah blok int main() , blok ini digunakan untuk memanggil fungsi-fungsi yang terdapat pada blok program selanjutnya kemudian untuk menginput serta mencetak output program tersebut.

Dalam setiap program harus ada pendeklarasian agar setiap variable yang digunakan tidak terdapat error serta menghindari penggunaan variable yang tidak dikenal oleh program.

int cost[N][N],i,j,w,ch,co;

int source, target,x,y;

Header program dibuat agar setiap penggunanya dapet mengerti mengenai program yang mereka kerjakan. Header tersebut ditulis dengan sintaks sebagai berikut:

printf("\t****Lintaan Algoritma Terpendek (DIJKSRTRA's ALGORITHM)****\n\n");.

Kemudian gunakan dua fungsi for awal untuk me-looping dari suatu graf yang telah dibuat pada blok program int dijstra yang mana blok tersebut menggunakan I,,j serta N sebagai varable…..

for(i=1;i< N;i++)

for(j=1;j< N;j++)

cost[i][j] = IN; .

Setelah itu dua for selanjutnya digunakan untuk memastikan simpul yang berhubungan yaitu ditandai dengan variable x dan y berturut dan akan saling terhubung hngga bertemu antara simpul 4 dan 5. x dan y merupakan pendeklarasian jalur simpul mana saja yang terhubung dan akan di input oleh bobot atau nilai antara simpul yang saling terintegrasi yang disebut dengan jarak yang didefinisikan tadi. Variabel yang digunakan untuk input nilai menggunakan w yang mewakili weight.

for(x=1;x< N;x++)

{

for(y=x+1;y< N;y++)

{

printf(" Masukkan nilai dari jalur antara simpul %d dan %d: ",x,y);

scanf("%d",&w);

cost [x][y] = cost[y][x] = w;

}

printf("\n");

}

Kemudian inputan pada simpul awal yang akan dicari nilai terdekatnya dengan simpul berikutnya, dimana &source merupakan variabel dari simpul yang akan dicari.

printf("\n Masukkan asal simpul: ");

scanf("%d", &source);

Setelah menginput awal simpul kemudian menginput target simpul yang akan dicari, dimana variabel &target merupakan tujuan terakhir untuk mencari nilai terdekatnya.

printf("\n Masukkan target simpul: ");

scanf("%d", &target);

setelah itu mencetak nilai terdekat yang didapatkan dari hasil mencari pada program dari setiap jalurnya dengan mencari nilai terkecil dengan memanggil co sebagai variabelnya yang ada dalam blok program diatas.

co = dijsktra(cost,source,target);

printf("\n Jalur Terpendek: %d",co);

setelah semuanya selesai maka langkah selanjutnya adalah mencoba programnya. Seperti yang tertera pada gambar dibawah ini.

Tampilan awal program: