Shortest Path Problem (Djikstra algorithm)

lAdalah salah satu permasalahan ‘mudah’ saat mempelajari materi tentang graph, yaitu dengan mencari cost dari jalur terpendek (jalur dengan cost terendah) dalam suatu graph. Ada beberapa algoritma yang dapat digunakan untuk memecahkan permasalahan ini, antara lain yang cukup terkenal adalah Bellman Ford dan Djikstra. Namun, masing-masing algoritma tersebut memiliki kelemahan dan kelebihan, semisal dari segi efisiensi antara Bellman Ford dan Djikstra yang lebih efisien adalah Djikstra, akan tetapi dalam beberapa kasus Bellman Ford lebih unggul yaitu jika salah satu cost dari edgenya ada yang bernilai negatif, hal ini disebabkan algoritma Djikstra hanya bisa dipakai jika semua cost dari edgenya tidak bernilai negatif. Dan kali ini, saya akan mencoba membahas bagaimana algoritma Djikstra bekerja.

Algonya sederhana. kita mulai dulu dari vertex awal/sumber dan kita anggap sebagai vertex fokus (begitu saya menyebutnya, vertex yang digunakan untuk mengupdate value dari semua vertex neighboor). Sebelumnya semua value dari vertex yang ada kita beri nilai infinite(nilai yang sangat besar, atau kalo diimplementasikan dalam program dengan nilai maksimum integer / 0x7FFFFFFF). Setelah itu kita beri value dari vertex awal tersebut dengan 0. Lalu updatelah value semua vertex neighboor dengan nilai minimum antara value fokus+cost edge ke vertex neighboor dengan value vertex neighboor atau kita bisa sebut dengan min(value fokus+cost edge ke vertex neighboor, value vertex neighboor), setelah itu kita beri tanda vertex awal tersebut dengan flag visited (true). semua vertex neighboor kita simpan dalam priority queue, dan kita pilih dari vertex neighboor itu yang paling rendah (minimal) valuenya untuk dijadikan sebagai vertex fokus. Lalu lakukan hal yang sama dengan langkah sebelumnya updatelah nilai value dari semua vertex neighboor dari vertex fokus, lalu simpan semua vertex neighboor dalam priority queue yang belum divisit (flag visited bernilai false), jangan lupa setelah mengupdate nilai semua vertex neighboor beri vertex fokus hendaknya diberi flag visited (true). setelah itu pilih vertex neighboor dengan value terendah dari priority queue untuk dijadikan sebagai vertex fokus. begitu seterusnya sampai vertex dalam priority queue habis. Dan dengan begitu kita bisa mendapatkan shortest path dari vertex awal / sumber ke semua vertex yang lain.

berikut saya ada link soal Shortest Path Problem : Travel

dan ini solusi yang saya buat untuk problem ini :STP.pdf

kalo ada yang belum jelas bisa tanya gw lwt email

atau comment

6 Responses so far »

  1. 1

    Felix J said,

    Selain pake djikstra, soal ini bs di ‘attack’ pake all-pair shortest path karna jumlah vertex yang ckup sedikit😀 <= 1000

    dan walaupun solusi all-pair shortest path ini lebih lambat, tapi di kontes bisa di pake untuk mencuri start dengan poin yang lumayan cepat..😀 (karena codingnya yang singkat😀 )

    REP REP REP …. selesai😛

    nice tutorial btw…🙂

  2. 2

    suhendry said,

    @felixj:
    siapa yang ngajarin kalau jumlah vertex <= 1000 bisa pake all-pair shortest path?

  3. 3

    marcadian said,

    hmm mungkin coachnya…sapa yaaaa coachnyaa?? **lirik lirik yang atas**

  4. 4

    whateva said,

    hihihihi… felixj ntar kamu harus ikut remedial yak! :p :p :p

  5. 5

    Petr said,

    @felixj: Kalo Floyd-Warshall utk n = 500 aja udah TLE kalo TL nya 1 detik…

  6. 6

    kak…saya mohon ijin copas gambar djikstra nya yah..buat di blog saya


Comment RSS · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: