Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path to all nodes in a weighted graph from a specified starting node.

Dijkstra's algorithm is a good example of a greedy algorithm, one that tries to follow the best-looking possibility at each step.

The basic idea is simple:

• Set the cost of the start node to 0, and all other nodes to ∞.

• Let the current node be the lowest-cost node that has not yet been visited. Mark it as visited. For each edge from the current node, if the sum of the cost of the current node and the cost of the edge is less than the cost of the destination node,
  • Update the cost of the destination node.

  • Set the parent of the destination node to be the current node.

When we get done visiting all nodes, each node has a cost and a path back to the start; we can reverse that to get a forward path.