====== 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.

===== Dijkstra's Algorithm =====
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.