Algoritma Djikstra Beserta Contoh Progamnya

ALGORITMA DJIKSTRA BESERTA CONTOH PROGAMNYA

 

Algoritma Dijkstra, (penemunya adalah seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.

Tujan Algoritma Dijkstra

• Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya.
• Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.
• Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra.

Urutan Logika Algoritma Dijkstra

1. Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).
2. Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.
3. Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.
4. Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
5. Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

Contoh :

Titik mengambarkan lokasi dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Pertama tentukan titik yang akan menjadi nomor kode (node) awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, lalu akan dilakukan pengembangan pencarian dari satu titik ke titik selanjutnya (tahap demi tahap).

1. Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar node telah diberi nilai
2. Dijkstra melakukan kalkulasi terhadap node tetangga yang terhubung langsung dengan node keberangkatan (node 1), dan hasil yang didapat adalah node 2 karena bobot nilai node 2 paling kecil dibandingkan nilai pada node lain, nilai = 7 (0+7).
   
   
3. Node 2 diset menjadi node keberangkatan dan ditandai sebagi node yang telah terdatangi. Dijkstra melakukan kalkulasi kembali terhadap node-node tetangga yang terhubung langsung dengan node yang telah terdatangi. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi terakhir, nilai 9 (0+9).
   
4. Perhitungan berlanjut dengan node 3 ditandai menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11 (9+2).
   
5. Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 (node tujuan ) telah tercapai lewat node 6. Jalur terpendeknya adalah 1-3-6-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai.

 Dan ini adalah contoh programnya dengan menggunakan C++:

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
int a[100];
int max, min;
void maxmin(int i, int j) {
int max1, min1, mid;
if (i==j) {
max=min=a[i]; }
else if(i==j-1) {
if (a[i]>a[j]) {
max=a[i];
min=a[j]; }
else {
max=a[j];
min=a[i]; }
}
else {
mid=(i+j)/2;
maxmin(i, mid);
max1=max;
min1=min;
maxmin(mid+1, j);
if (max<max1)
max=max1;
if(min>min1)
min=min1; }
}
void main() {
int i, num;
clrscr();
printf("\n\t\t>>Algoritma Divide & Conquer");
printf("\n\t\t>>Kelompok 1:\nJeni\tIndah\tTetem\tHuda\tYusuf\tAsif\tSilmi\tArif\n>>Teknik Informatika");
printf("\n\t\t\t Program Maximum & Minimum \n\n");
printf("\nMasukkan  Jumlah Angka: ");
scanf("%d", &num);
printf("\nMasukkan Angkanya: \n");
for(i=0;i<num;i++) {
scanf("%d",&a[i]); }
max=a[0];
min=a[0];
maxmin(0, num-1);
printf("\nNilai Maximum Angka: %d\n",max);
printf("Nilai Minimum Angka: %d\n",min);
getch();
}

Inilah hasilnya: