index.md (856B)
1 +++ 2 title = "Dijkstra's algorithm" 3 +++ 4 # Dijkstra's algorithm 5 What is it? 6 7 Solves the single-source shortest path problem — find shortest path from one designated node to every other node. 8 9 Only works with non-negative edge weights. 10 11 Steps: 12 1. Take the starting node 13 2. Compute the distances to every other connected node (just follow the edges from the starting node) 14 3. Take the smallest edge, and follow it to a new node 15 4. Use the edges from the new node to update the table, and possibly create new/smaller paths to other nodes 16 5. Take the new smallest edge to a node that was not visited yet 17 6. Repeat from step 4 18 19 **Methods:** 20 21 | **Graphical** | **Tabular** | 22 | --- | --- | 23 |  |  |