Source
Code Algoritma Djikstra
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);
Tampilan awal program:
Tampilan program pada proses input:
Tampilan Outputnya seperti dibawah ini hasilnya:
Tidak ada komentar:
Posting Komentar