Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:david:chapter4 [2011/02/16 06:25] – [4.2 - Scheduling to Minimize Lateness: An Exchange Argument] margoliesd
+++ courses:cs211:winter2011:journals:david:chapter4 [2011/02/16 06:31] (current) – [4.4 - Shortest Paths in a Graph] margoliesd
@@ Line 13: / Line 13: @@
 Readability: 7/10
 ====4.4 - Shortest Paths in a Graph====
+Our problem is to find the shortest path between two nodes, assuming that are starting node has a path to ever other node in the graph, and that each edge has a specific length associated with it. Dijkstra's algorithm adds the next node with the shortest length to the current set of nodes. We use a priority queue to store the edge lengths and then use the extractMin operation to get the next shortest length.The algorithm has an efficiency of O(m) if we use priority queues.
+Readability: 6/10 because it is a fairly confusing algorithm to follow