Tham khảo tài liệu 'thuật toán algorithms (phần 43)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | WEIGHTED GRAPHS 413 priority-first search method will be faster for some graphs Prim s for some others Kruskal s for still others. As mentioned above the worst case for the priority-first search method is while the worst case for Prim s is and the worst case for Kruskal s is Elog But it is unwise to choose between the algorithms on the basis of these formulas because graphs are unlikely to occur in practice. In fact the priority-first search method and Kruskal s method are both likely to run in time proportional to E for graphs that arise in practice the first because most edges do not really require a priority queue adjustment that takes logV steps and the second because the longest edge in the minimum spanning tree is probably sufficiently short that not many edges are taken off the priority queue. Of course Prim s method also runs in time proportional to about E for dense graphs but it shouldn t be used for sparse graphs . Shortest Path The shortest path problem is to find the path in a weighted graph connecting two given vertices x and y with the property that the sum of the weights of all the edges is minimized over all such paths. If the weights are all 1 then the problem is still interesting it is to find the path containing the minimum number of edges which connects x and y. Moreover we ve already considered an algorithm which solves the problem breadth-first search. It is easy to prove by induction that breadth-first search starting at x will first visit all vertices which can be reached from with 1 edge then all vertices which can be reached from x with 2 edges etc. visiting all vertices which can be reached with k edges before encountering any that require k 1 edges. Thus when y is first encountered the shortest path from x has been found because no shorter paths reached y . In general the path from to y could touch all the vertices so we usually consider the problem of finding the shortest paths connecting a given vertex x with each of the other .
