SHORTEST PATH (LINTASAN TERPENDEK)

SHORTEST PATH (LINTASAN TERPENDEK)
Jika diberikan sebuah graph berbobot, masalah lintasan terpendek adalah bagaimana kita mencari sebuah jalur pada graph yang meminimumkan jumlah bobot sisi pembentuk jalur tersebut.
Terdapat bermacam persoalan lintasan terpendek antara lain:
1. Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path).
2. Lintasan terpendek antara semua   pasanggan simpul (all pairs shortest path).
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shortest path).
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).

Algoritma-Algoritma Shortest Path
1.Algoritma Greedy

2. Algoritma Djikstra
3.Algoritma Bellman-Ford
4.Algoritma Branch and Bound (B&B)
5.Algoritma Koloni Semut
6.Algoritma Floyd-Warshall
7.Algoritma Genetik
8.Algoritma Perkalian Matriks
9.Algoritma Label Correcting (Pengoreksian Label)
10.Algoritma A*
11.Algoritma PHA
12.Algoritma Johnson
13.Algoritma Exhaustic Search
14.Algoritma UCS ( Uniform Cost Search )

Penyelesaian Masalah Single Pair

1. Algoritma Greedy

Langkah-langkah:

a.  Menentukan  titik sebagai titik awal dan titik tujuan.

b.  Evaluasi semua sisi yang terkait dengan titik awal. 

c.  Pilih sisi dengan bobot yang paling minimum.

d.  Maka diperoleh titik baru yang terhubung langsung dengan titik awal. 

e. Dimulai dari titik yang diperoleh pada langkah 4, ulangi langkah 2 hingga sampai ke titik tujuan. 

2. Algoritma Djikstra

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 (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. Saat kita 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 

3. Algoritma Exhaustic Search

Mencari lintasan terpendek dengan Exhaustive Search yaitu dengan mengenumerasi setiap lintasan

yang mungkin dengan cara yang sistematis. Dari setiap kemungkinan tersebut dievaluasi satu persatu,

selanjutnya bandingkan setiap lintasan yang telah dievaluasi, lintasan yang memberikan nilai terkecil

merupakan lintasan terpendek yang kita cari.