Chapter 4.4: Shortest Paths in Graphs

It is possible to use a greedy algorithm to find the shortest path in a graph, whether the graph is directed or undirected, weighted or unweighted.

This algorithm maintains a set S of vertices u for which we have determined the shortest path distance d(u) from s. We call this the “explored” part of the graph. Initially, S={s} and d(s)=0. For each node v in V-S, we determine the shortest path that can be constructed by traveling along a path through the explored part S to some u in S, followed by the single edge (u,v). We consider d'(v)=min_e(u,v) d(u)+l_e. We choose the node v in V-S for which this quantity is minimized and add v to S and define d(v)=d'(v).

This can be clarified by the pictures used in the lecture slides.

At any point in the algorithm, the path P_u is the shortest s-u path. This algorithm fails if edges have negative lengths. It is also important to note that Dijkstra's Algorithm is a continuous version of the standard BFS used to traverse graphs.

Using a priority queue, Dijkstra's Algorithm can be implemented on a graph with n nodes and m edges to run in O(m) time, plus the time for n ExtractMin and m ChangeKey operations. So the overall running time is O(mlogn).

I would rate this section an 8. It was easy to read but the lecture was easier to understand.