Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
courses:cs211:winter2011:journals:wendy:chapter4 [2011/02/16 02:08] โ [Section 4: Shortest Paths in a Graph] shangw | courses:cs211:winter2011:journals:wendy:chapter4 [2011/02/16 08:25] โ [Section 4: Shortest Paths in a Graph] shangw | ||
---|---|---|---|
Line 27: | Line 27: | ||
===== Section 4: Shortest Paths in a Graph ===== | ===== Section 4: Shortest Paths in a Graph ===== | ||
+ | This section introduces the third example of greedy algorithm: finding the shortest paths. | ||
+ | The problem is just as what its name describes, given a directed graph, assigned a node s, how to find the path from s to every other node that is the " | ||
+ | |||
+ | After the discussing the theory aspects of the Dijkstra algorithm, the section further talks about the best way to implement the algorithm, using priority queue. Indeed, in class, I felt that we do not need all operations from PQ-the insert part will be linear even just treating it as a list. For each iteration, we need to add an node v to the set S, to select the right v-based on d(v)-the ExtractMin is used; to update d(v) for all nodes involved in the iteration, we use changeKey. ExtractMin is used at most n time and each time it takes o(logn); ChangeKey is used at most for all edges, m , times and each time it also takes o(logn). Hence, overall, the running ime is o(mlogn). | ||
+ | |||
+ | The algorithm is greedy because every iteration it only picks the node that a shortest path between it and s is the smallest under all circumstance. It is very smart. | ||
+ | |||
+ | The readability is 8. |