Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | Next revisionBoth sides next revision |
| courses:cs211:winter2011:journals:wendy:chapter4 [2011/02/16 02:37] – [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 |
|---|
| This section introduces the third example of greedy algorithm: finding the shortest paths. | 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 "lightest". Dijkstra came up with an algorithm to solve the problem, namely, the Dijkstra algorithm. The idea of Dijkstra algorithm is to keep track of the current shortest path and keep updating during the exploration of the graph. | 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 "lightest". Dijkstra came up with an algorithm to solve the problem, namely, the Dijkstra algorithm, which is presented in the book. If we want to output the detailed information of each shortest path, just keep track of the added edge at each iteration. To prove the validity of the algorithm, we show that the solution selected by the algorithm "stays ahead" from other possible solutions using inductions. Note that the Dijkstra algorithm only works when all edges are positive numbers; otherwise the solution does not necessarily stay ahead. The book also provides anther insight of the algorithm: BFS traversing the graph. This intuitively makes sense to me: because each iteration we look at the next level-one distance away from the set S. The book uses an analogy of water expand, but I personally did not find it too helpful, though the insight is nice to know. |
| | |
| | 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. |
