Is this a correct description of Dijkstra's algorithm

Question

I am on a journey understanding Dijkstra's algorithm.

My familiarity with mathematical terms is not great, so I have put the algorithm into my own English. I understand this is not ideal, but this is part of my learning process.

What are the major areas of misunderstanding in the description below?

---

We maintain a list D of all the tentatively known shortest distances to nodes.

Each item in D comprises a node name, a shortest (yet known) distance and a "via" node, indicating the node the path arrives via.

ie. [{ node, tentativeDistance, via }, ...]

We start with a list G of all the nodes in the graph.

ie. [{ name, edges }, ...]

We use G to keep track of the nodes we have visited. Each time we visit a node we remove it from G. In this way we never visit a node more than once.

We pull a node N from G. At the start we pull the start node with cumulative distance of zero.

If this is the start node we add it to D.

We calculate the cumulative distance to it, given the node we have arrived via. At the start we arrive via itself.

eg. if we arrived at node C via node B, we know that the shortest path to B is, say, 2 because we must have previously explored other options to arrive at B; if the cost of the edge from B to C is 1 the cumulative distance is 2 + 1 = 3.

We then review the unfollowed edges from every node that we have visited already (in D). This is akin to choosing which part of the advancing "wavefront" to advance from.

For each of the unfollowed edges if the cumulative distance to the destination node is shorter than any previously recorded distance for that node in D (or we do not yet have a distance for it) then we replace (or add) the entry for the node in D, together with the "via" value (the current node). In this way we build up a list of best-known distances to nodes.

We pick the new destination node with the shortest cumulative distance.

Again: in this way, we can be confident that when we arrive at a node, we have found the shortest path to it.

When we arrive at the destination node, or when we have visited all the nodes we stop, otherwise we repeat the edge-reviewing process described above.

Answer 1

Not bad. May I suggest a few improvements?

• Distinguish between the algorithm (what you do) and the argument (the proof of why it works).
• Your D, which you say is a list, is better thought of as a map/associative-array from Node to [distance, Node], where the former Node is the predecessor of the latter.
• Start the computation with {start-node -> [0, nil]} in D.
• Define the graph G as a mapping Node -> Set of [distance, Node], where the distance is the edge length from the former to the latter node. This makes the iterative step easier to describe precisely.

---

The point of Dijkstra's algorithm is that the tentative distances turn out to be final. The way to prove this is to show that - given that it is true of D so far - it is true at the next step too. This is called the inductive hypothesis. Given that it is true of the initial D, which it is, it is true of all the Ds thereafter, including the final one.