There seemed to be some confusion on how Dijkstra's Algorithm works when pseudo coded/coded. If you understand the way we used generic programming with sequence structures to get BFS and DFS this shouldn't be too bad.
The pseudo code for using sequence structures with BFS and DFS is as follows:
SequenceStructure seq = new SequenceStructure();
seq.add(startNode);
while( !seq.isEmpty() )
node n = seq.get();
process(n);
add all neighbors of n not already processed to seq;
With the above algorithm if the sequence structure changes the search changes. If we use a queue as the sequence structure we get a BFS, while using a stack will yield a DFS.
We begin by placing the start node into the sequence structure. Then we grab a node from the sequence structure, process it, and add all of the node's neighbors that we have not processed yet to the sequence structure. By the time the sequence structure is empty we will have processed all the nodes in the graph.
If we first think about storing edges in the sequence structure instead of nodes it will help us in understanding Dijsktra's Algorithm. Dijsktra's Algorithm deals with shortest path therefore we are concerned about the edges connecting nodes.
If we change the sequence structure to be a priority queue (the smaller the priority the better) (or a min heap) where the priority or value of the edge is the minimum length path from some root node r, we basically get Dijsktra's algorithm.
SequenceStructure seq = new SequenceStructure();
seq.add(rootEdge, priority=0); // in lecure it was dummyRoot, think of this as the edge connecting the start node to itself, it therefore has a length of 0
while( !seq.isEmpty() )
edge e = seq.get(); // edge e connect a node L to a node F. Node L has already been discovered and node F is the newly discovered node
node F = edge.getEndPoint(); // F is the end point of the edge grabbed from the sequence structure
if we have not already discovered F;
place F in our discovered node list;
set the minDistance to F to be the min distance to node L (the "parent" of L, the node on the other end of edge e), plus the length of edge e;
for each edge that has F as one of the nodes (edges of the formF->N for some node N)
if node N is not already discovered
place the edgeconnecting F->N into the sequence structure with priority minDistance to F + length of edgedF->N
Now let's see why this makes sense.
We get the algorithm started by placing in a dummy edge which connects the start node to itself. This edge has a length of 0 since the distance from a node to itself is 0.
We then grab the edge (L->F) with the minimum cost and check to see if one of the nodes that form this edge has not yet been discovered (if it has been discovered than there already exists a shorter path to this node since it was removed from our priority queue before this edge was).
If the node F has not been discovered it now has been. The minimum cost to this node F is going to be the minimum cost to the node L plus the length of the edge connecting L and F (this is exactly the shortest path we were looking for).
We now examine the edges leaving F (F->N). If the node on the other end of the edge leaving F has not been discovered yet this edge should be added to the sequence structure of edges to process. Now we just need to decide what priority this edge should receive. Since we are looking for shortest paths it should include the minimum distance to F + the length of itself.
When this ends the sequence structure will be empty and we will have discovered every node and the minimum distance to each node.