资料结构和演算法(下).pptVIP

2009/3/6 Shortest Path Tree 資料結構與演算法(下) 呂學一 (Hsueh-I Lu) .tw/~hil/ Today Shortest path and cycle Shortest-Path Tree Bellman-Ford Lawler Dijkstra The settings Shortest path and cycles Question Observation Shortest-path tree problem The problem Without loss of generality We may assume that each node in the graph is reachable from r. Why? Unreachable nodes can be removed in linear time by a depth-first search starting from r. Also known as Single-source shortest-path problem The root r is the “source”. Question Such a shortest-path tree always exists? Perhaps not.. As a matter of fact The input graph G has a shortest-path tree if and only if G does not contain any negative cycle. The only-if direction is “obvious”. If a node u belongs to a negative cycle, then there is no shortest path from r to u. Q: how about the other direction? 從r到u一定有shortest path 雖然從r到u的path可能有無窮多條（因為G可能有cycle），但是根據G沒有negative cycle，我們可以說明從r到u一定有一條shortest path： 因為G沒有negative cycles, 所以任何包含cycle的path，在去掉cycle之後不會增加長度。 沒有cycle的paths只有finite條，其中最短的任何一條一定就是從r到u的shortest path。 但是union起來未必就是答案 G has no negative cycle Removing cycles from a path does not increase it length. For each node u of G, there has to be a shortest path from r to node u that do not contain any cycle. Some “adjusted” union of all these n shortest paths yields a shortest-path tree of G rooted at r. An equivalent problem The shortest-path tree problem is equivalent to finding the distance from r to each node u in graph G. The distance from r to node u in G is the length of any shortest path from r to u in G. By “equivalence” we mean that a solution to either problem can be obtained from a solution from the other problem in linear time. Why? Tree ? distance Tree ? distance Example The rest of the slide Let d(u) denote the distance from r to u in graph G. We focus only on computing the distance of each node u from r. Without loss of generality, we may assume that the distance of each node from r is finite. That is, each node is rea