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/28 23:43] โ 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. | ||
+ | |||
+ | ===== Section 5: The Minimum Spanning Tree ===== | ||
+ | This section talks about how to obtain the minimum spanning tree from a connected graph through the 3 different greedy algorithms. | ||
+ | |||
+ | First the definition of minimum spanning trees is introduced: a spanning tree, that is an acyclic path connecting all the nodes, that has minimum weight. | ||
+ | There are three greedy algorithms to solve the problems, namely: | ||
+ | 1, The Kruskal' | ||
+ | 2, Prim's Algorithm that starts with a node and greedily grow outward using the analogy of Dijkstra' | ||
+ | 3, the Reverse-Delete Algorithm that deletes edges from an descending order if deleting the edge does not disconnect the graph. | ||
+ | |||
+ | Then the book continues to analyze the algorithms. Before getting into each algorithm, it first introduces two important properties (actually the second is introduced after the analysis of Kruskal and Prim's algorithm, just for simplicity, I group them together): | ||
+ | 1, the cut property: if all edges are of distinct values, the minimum-weighted edge that connecting two non-empty, disconnected subsets need to be in the minimum spanning trees. | ||
+ | 2, the cycle property: for a cycle, the maximum-weighted edge in the cycle is not in the minimum spanning tree. | ||
+ | |||
+ | Use the cut property we can prove Kruskal and Prim's algorithms easily, especially the Prim one, very straightforward. | ||
+ | Use both properties to prove the Reverse-Delete algorithm: when deleting an edge is possible, use circle property; when not, cut property. | ||
+ | In general, deleting is justified by Circle property, and inserting by Cut property, no matter what kind of greedy algorithm we used, which also explains the variety of greedy algorithms. | ||
+ | |||
+ | Before, we assume that all edges are of distinct values. The method to get rid of this assumption is the perturb the ties with very small value epsilon, that is, forcing an order, and then use those algorithms. | ||
+ | |||
+ | After analyzing the algorithm, naturally follow the implementations of those algorithms, except for the Reverse-delete algorithm when the running time is hard to reach O(mlogn). This section only introduces the implementation of the Prim's Algorithm through priority queue like in Dijkstra' | ||
+ | |||
+ | However, in practice, minimum spanning tree is not enough for a smoothly-run network. There are problems such as for individual pairs, the client may not be willing to have an edge that is heavy-weighted, | ||
+ | |||
+ | The readability is 7. |