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.
Sumber : firstqien.blogspot.co.id
