ePhysics

Because we've gone a couple weeks without class, we won't introduce new material in this class. There will be no homework due next week. The purpose of this class is simply to refresh what we've covered over the past several class periods.

First, let's review Dijkstra's algorithm.

Now, let's review an example of applying Dijkstra's algorithm to a graph.

Here's a graph:

As we always, we start out by writing (-,∞) next to each node (I wrote "inf" in the image simply because my image editor doesn't support special characters) and mark the starting node (node A) as visited (Note that in these images, I'm using red to denote a visited node).

Next, we find the distances to all the nodes connecting to the current node (node A) — that's nodes B, C, and D. These distances are all less than the previous values (infinity), so we replace the values with the distances to starting node:

Next, we find the node which has the  lowest total value. Node C has value 1, B has balue 2, D has value 2, and the rest are still infinite. The lowest is C, so we mark C as visited and find the distances to the unvisited nodes connecting to C. The unvisted nodes connecting to C are B, E, and F (A is also connected to C, but it has been visited. So we don't worry about it). First, let's consider node B — the distance between C and B is 3 and C's current value is 1, so the total distance to B through C is 3+1=4, which is NOT less than B's current value of 2, so leave B alone. The total distance to E through C is 3+1=4, which is NOT less than E's current value of 4, so leave E alone as well. And the total distance to F through C is 2+1=3, which is less than infinity. So update F's value:

Again, we find the unvisited node with the lowest value. There's a tie between B and D. We (arbitrarily) pick B. Considering the unvisited nodes connecting to B (D and E), we find that distances to these nodes through B are greater than the values they already have, so we leave them alone:

Now, the least valued unvisited node is D. Mark it as visited and again observe that none of the connecting unvisited nodes have a lower total distance going through B, so we don't have to update anything:

Now, the least valued unvisited node is F. We mark it as visited, and … well, we just marked the ending node as visited, which means we stop (we're done). So, we know that the shortest distance between the starting and ending nodes is equal to F's value (3). We see that F comes from C and C comes from A, so the shortest path is A→C→F.

Remember: Dijstra's algorithm gives a shortest path, not the shortest path. Is there another "shortest" path in this graph? Note that if there exists another shortest path, it cannot be shorter than we found, so this isn't a problem.

Now, let's review the flow chart for Dijkstra's algorithm. Here's the "big picture" flow chart:

 

 

As previously observed, we need to do some more work befor translating this flow chart into Python code. Next week, we'll make more detailed flow charts of the boxes marked "Loop through nodes which…" and "Find the least valued node…"