cara mencari jalur terdekat dengan menggunakan algoritma djikstra dan algoritma floyd warshall
Bila ingin mencari jalur terpendek dengan menggunakan dengan menggunakan
algoritma djikstra kita harus melalui step by step dengan cara cari jalur terpendek dahulu sebelum pindah ke tempat selanjutnya. Sedangkan jika kita menggunakan algoritma
floyd warshall, kita harus mengakumulasikan seluruh jalur sebelum kita jalan kejalur selanjunya. Dengan cara kita menitung terlebih dahulu seluruh jalur yang menuju kota yang akan kita tuju.
Contoh kasus:
|
Add caption |
Keterrangan:
Kasus disini, kita ingin mencari jalur terpendek dari kota A ke kota G dengan menggunakan algoritma djikstra. Hal yang pertama yang kita lakukan ialah, kita lihat diatas jalur yang ada dari kota A ada 3 jalur, yaitu ke kota B (5km),C(7km) dan F(10km). Setelah kita mengetahuinya, maka kita cari jalur yang paling pendek. Ternyata jalur yang terpendek merupakan jalur yang menuju ke kota B(5km), jadi kita menuju ke kota B. Setelah itu kita lihat jalur B yang memiliki 2 jalur yaitu jalur menuju kota C(6km) dan D(3km). Stelah kita mengetahuinya, ternyata jalur terpendek dari kota B yaitu ke kota D(3km). Lalu kita lihat jalur D yang hanya memiliki 1 jalur yaitu jalur yang menuju kota E(3km) dengan demikian jalur E yang kita pilih. Dari kota E, kita memiliki 2 jalur, yaitu ke kota F(3km) dan G(4km). Karena jalur yang terpendek merupakan jalur yang menuju kota F(3km), jadi kita pilih jalur yang menuju ke kota F. Dari ko F kita tinggal menuju kota G(4km). Setelah diakumulasi, jadi jalur yang ditempuh sepanjang 5km+3km+3km+3km+4km=18km bila kita menggunakan algoritma djikstra.
|
Add caption |
Tadi kita sudah menghitung jalur terpendek dari kota A ke kota G dengan menggunakan algoritma djikstra. Sekarang kita akan mencoba menghitung kembali jalur yang sama dengan menggunakan algoritma floyd warshall. Tahap yang akan kita lakuan sebelum jalan, kita harus menghitung seluruh jalur yang menuju kota yang akan kita tuju.
1. A F G
Jarak yang ditempuh, 10km + 4km = 14km
2. A C E G
Jarak yang ditempuh, 7km + 4km + 4km = 15km
3. A C E F G
Jarak yang ditempuh, 7km + 4km + 3km + 4km = 18km
4. A B C E F G
Jarak yang ditempuh, 5km + 6km + 4km + 3km + 4km = 22km
5. A B D E F G
Jarak yang ditempuh, 5km + 3km + 3km + 3km + 4km = 18km
6. A B D E G
Jarak yang ditempuh, 5km + 3km + 3km + 4km = 15km
Setelah kita hitung keseluruhan, lalu kita lihat jalur terpendek yang dari kota A ke kota G. Disini kita dapat jalur terpendek yaitu jalur A,F,G dengan total jarak 14km.
Dengan demikian kita dapat mengambil kesimpulan:
jadi dari kedua cara yang ada, cara dengan menggunakan algoritma floyd warshall lebih efektif dibandingkan dengan menggunakan cara algoritma djikstra.
BAGUS DAN MTRNWUN