Contoh Masalah & Penyelesaian Algoritma Djikstra & Floyd Warshall

Assalamualaikum Wr.Wb, Kali ini saya akan membahas sedikit tentang Algoritma Djikstra & Floyd Warshall

    Algoritma Djikstra adalah salah satu pemecahan persoalan terkait masalah optimasi pencari lintasan terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a ke z dalam graph berbobot, bobot tersebut adalah bilangan positif yang tidak dapat dilalui oleh node negatif, jadi secara ringkasnya adalah mencari jalan terpintas atau jalan tercepat dalam suatu lintasan tersebut.

    Floyd Warshall adalah satu varian dari pemprograman dinamis,metode memecahkan masalah pencarian rute terpendek (sama seperti Algoritma Djikstra), Metode ini memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait.Maksudnya solusi-solusi itu dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan lebih dari satu.

Contohnya yaitu sebagai berikut

• Tentukan jalur terpendek atau jalur tercepat dalam lintasan tersebut
• Cari rute dari titik 0 ke 5 sebanyak mungkin
• langkah yang diambil tidak boleh berlawanan arah dengan tanda panah

Baiklah begini penyelesaiannya menurut Algoritma Djikstra :

1. dari titik 0,terdapat dua arah yaitu ke titik 1 Jl.Agus (13km) dan ke titik 2 Jl.Eri (4km),dari sini kita mengetahui kalau jalur tercepat itu adalah dari titik 0 ke titik 2 Jl.Eri (4km).
2. dari titik 2,ternyata hanya melalui satu arah yang tercepat yaitu ke titik 4 Jl.Farhan (1km).
3. dari titik 4,terdapat dua arah yaitu ke titik 3 jl.Gigi (5km) dan ke titik 5 Jl.Halim (13km),dari sini kita mengetahui jalur tercepatnya yaitu dari titik 4 ke titik 3 Jl.Gigi (5km).
4. dari titik 3,ternyata hanya melalui satu arah yang tercepat yaitu ke titik 5 Jl.Cinta (5km)

jadi kesimpulan totalnya jalur tercepat yaitu (4Km + 1Km + 5Km + 5Km) = 15Km.

tadi adalah penyelesain Algoritma Djikstra,sekarang kita coba penyelesaiannya dengan menggunakan Floyd Warshall

1.   0 - 2 - 4 - 3 - 5 (4Km + 1Km + 5Km + 5Km = 15Km)
2.   0 - 2 - 4 - 5 (4Km + 1Km + 13Km = 18Km)
3.   0 - 1 - 3 - 5 (13Km + 6Km + 5Km = 24Km)
4.   0 - 1 - 2 - 4 - 3 - 5 (13Km + 2Km + 1Km + 5Km + 5Km = 26Km)
5.   0 - 1 - 2 - 4 - 5 (13Km + 2Km + 1Km + 13Km = 29Km)

Terdapat 5 jalur yang bisa diselesaikan dari titik 0 - titik 5, jalur tercepat atau jalur terpendek pun yaitu berada di nomor 1 dengan keseluruhan total jarak tempuh 15Km

Sekian penjelesan singkat tentang Algoritma Djikstra dan Floyd Warshall serta contoh penyelesaiannya,semoga apa yang saya sampaikan ke teman-teman bisa bermanfaat bagi kita semua,mohon maaf apabila ada kesalahan kata,saya ucapkan banyak terima kasih,tetap pantau blog saya untuk materi-materi yang akan saya bagikan

Assalamualaikum Wr.Wb