Shortest Path

F. Shortest Path

Pencarian shortest path (lintasan terpendek) adalah masalah umum dalam suatu weighted, connected graph. Misal : Pencarian jaringan jalan raya yang menghubungkan kota-kota disuatu wilayah.

1.    Lintasan terpendek yag menghubungkan antara dua kota berlainan tertentu (Single-source Single-destination Shortest Path Problems)

2.    Semua lintasan terpendek masing-masing dari suatu kota ke setiap kota lainnya (Single-source Shortest Path problems)

3.    Semua lintasan terpendek masing-masing antara tiap kemungkinan pasang kota yang berbeda (All-pairs Shortest Path Problems)

Untuk memecahkan masing-masing dari masalah-masalah tersebut terdapat sejumlah solusi.

Dalam beberapa masalah graph lain, suatu graph dapat memiliki bobot negatif dan kasus ini dipecahkan oleh algoritma Bellman-Ford. Yang akan dibahas di sini adalah algoritma Dijkstra yaitu mencari lintasan terpendek dari suatu verteks asal tertentu vs ke setiap verteks lainnya.

a. Graph berbobot (weighted graph)

Apabila sisi-sisi pada graph disertai juga dengan suatu (atau beberapa) harga yang menyatakan secara unik kondisi keterhubungan tersebut maka graph tersebut disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot tersebut merupakan "harga" dari keterhubungan antar vertex. Pengertian "harga" ini menggeneralisasikan banyak aspek, biaya ekonomis dari proses/aktifitas, jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya.

 Dalam beberapa masalah lain bisa juga bobot tersebut memiliki pengertian "laba" yang berarti kebalikan dari "biaya" di atas. Dalam pembahasan algoritma-algoritma graph nanti pengertian bobot akan menggunakan pengertian biaya sehingga apabila diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan dengan mencari laba maksimum. 

b. Algoritma Dijkstra’s

Algoritma Dijkstra's :

1.    Menyelesaikan problem single-source shortest-path ketika semua edge memiliki bobot tidak negatif.

2.    Algoritma greedy mirip ke algoritma Prim's.

3.    Algoritma di awali pada vertex sumber s, kemudian berkembang membentuk sebuah tree T, pada akhirnya periode semua vertex dijangkau dari S. Vertex di tambah ke T sesuai urutan

Misalnya :

Pertama S, kemudian vertex yang tepat ke S, kemudian yang tepat berikutnya dan seterusnya.

c. Dynamic Programming

Terdiri dari sederetan tahapan keputusan. Pada setiap tahapan berlaku prinsip optimality (apapun keadaan awal dan keputusan yang diambil, keputusan berikutnya harus memberikan hasil yang optimal dengan melihat hasil keputusan sebelumnya.

Misalnya  :     Multistage Graph

Dimana    :     Cost (i,j) = Min(C(j,l) + Cost(i+1,l)}

Dengan    :    C(j,l) = Bobot edge j dan l

l = Elemen Vi+1 Dan <j,l> eemen E

i=stage ke-I dan j = node dalam V

Proses dimulai dari k-2, dimana k adalah banyak stage.

Perhatikan contoh untuk menentukan biaya termurah dari 1 hingga 12.

Diketahui graph dengan stage sebagai berikut :

Maka langkah-langkah yang dilakukan adalah :

K=5, sehingga dimulai dari S3

Cost(3,6) = Min{6+Cost(4,9); 5+Cost(4,10)} = Min{6+4;5+2} = 7

Cost(3,7) = Min{4+Cost(4,9); 3+Cost(4,10)} = Min{4+4;3+2} = 5

Cost(3,8) = Min{5+Cost(4,10); 6+Cost(4,11)} = Min(5+2;6+5} = 7

Cost(2,2) = Min{4+Cost(3,6);2+Cost(3,7);1+Cost(3,8)}

= Min{4+7;2+5;1+7} = 7

Cost(2,3) = Min{2+Cost(3,6); 7+Cost(3,7)} = Min(2+7; 7+5) = 9

Cost(2,4) = Min{11+Cost(3,8)} = 18

Cost(2,5) = Min{11+Cost(3,7); 8+Cost(3,8)} = Min(11+5;8+7} = 15

Cost(1,1) = Min{9+Cost(2,2);7+Cost(2,3);3+Cost(2,4),2+Cost(2,5)}

= Min{9+7;7+9;3+18;2+15} = 16

Shorthest Path menjadi :

1 -> 3 ->  6 ->  10 ->  12 Atau  1 ->  2 ->  7 ->  10->  12

Jika ada dua atau lebih shorthest path maka total biaya harus sama.

Shortest Path Pertama adalah :

Shortest Path Kedua adalah :