Dijkstra’s algorithm, conceived by Dutch computer scientistEdsger Dijkstra in 1956 and published in 1959,[1][2] is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree.
Hoahmm, Okelah kalo Dijkstra tapi cuman ngecek bobot perjalanan aja, masih nggak terlalu susah lah implementasinya, tinggal ngeliat algoritma yang ada di wikipedia aja sih.
Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.
- Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
- Mark all nodes as unvisited. Set initial node as current.
- For current node, consider all its unvisited neighbors and calculate their tentative distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.
- When we are done considering all neighbors of the current node, mark it as visited. A visited node will not be checked ever again; its distance recorded now is final and minimal.
- If all nodes have been visited, finish. Otherwise, set the unvisited node with the smallest distance (from the initial node) as the next “current node” and continue from step 3.
Tapi ini tugas terakhir Struktur Data dan Algoritma, salah satu matakuliah yang paling wow di kampus saya.
Yok ah, deadlinenya Sabtu, masih banyak waktu hahahahaha #stress
Prahesa K Setia 