Dijkstra's Algorithm

• Given a graph with weighted non-negative arcs, find the shortest path between two points.
1. Assign a distance value to all nodes. 0 for the start node, and infinity for all others.
2. Mark all nodes as unvisited, and set the initial node as current.
3. Repeat until goal node is visited (or all nodes visited then fail).
   1. For the current node, visit all unvisited nodes that are connected. Give the appropriate distance to each of these nodes.
   2. Mark the current node as visited. Whack in the distance to it.
   3. Make the unvisited node with the smallest distance the current node.
• Assumes non-negative weights.