Second Topic - Circuit Switched Algorithm ( Dijkstra v.s. Bellman Ford )

Wah puyeng nih.. Itu yang terlintas ketika kita disuruh menentukan jalan terpendek menuju suatu tempat dengan berbagai alternatif rute.. Hmm itu juga yang terjadi pada proses pengiriman data (paket) pada sebuah jaringan Packet Switched.. Atau gampangnya seolah kita disuruh menset up sebuah jalur layaknya pada jaringan Circuit Switched..

Gak usah bingung lagi.. Nah kali ini akan coba2 nih diskusi tentang algoritma2 nya.. diantaranya Dijkstra dan Bellman Ford.. Yuk dibahas masing2 bedanya apa diantara kedua algoritma tersebut..

Dijkstra
Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah salah satu algoritma untuk memecahkan masalah “ single source shortest path”, untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif. Output algoritma dijkstra adalah spanning tree T, dimana path dari vertex s (sumber) ke masing-masing vertex v adalah sebuah shortest path dari s ke v dalam sebuah graph G.



Bellman-Ford
Algoritma ini merupakan pengembangan dari algoritma Djikstra. Algoritma Bellman Ford akan benar jika dan hanya jika graph tidak terdapat cycle dengan bobot negatif yang dicapai dari sumber s. Algoritma Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif.



Ada dua hal yang harus menjadi catatan pada algoritma Bellman-Ford, yaitu :
1. Shortest path tidak akan terdiri lebih dari V-1 edge dari graph yang bersangkutan, dengan asumsi tidak ada negative cycle.Jika terdapat lebih dari V-1 edge pada shortest path, maka ada node yang dilewati lebih dari satu kali.Hal tersebut akan mengakibatkan shortest path tidak optimal.
2. Pada tiap iterasi, harus dipertimbangkan edge mana yang akan digunakan terlebih dahulu

Okey sekarang jadi tau kan.. dan bisa memilih sendiri algoritma yang akan digunakan menyesuaikan dengan kondisi yang ada.. selain itu juga masih banyak algoritma2 yang lain.. Salah satunya yang lain adalah Floyd Warshall.. Selamat mencari.. -IR-