Johnson's演算法可用於计算All

1、Johnsons algorithm Johnsons演算法可用於計算All pairs shortest path問題。 在邊的數量不多的時候，如|E|=O(|V|log|V|)時，能有比Warshall-Floyd演算法較佳的效能。 其輸入需求是利用Adjacency list表示的圖。Graph reweightingTheorem. Given a label h(v) for each v V, reweight each edge (u, v) E by(u, v) = w(u, v) + h(u) h(v).Then, all paths between the same two

2、 vertices arereweighted by the same amount.Proof. Let p = v1 v2 vk be a path in the grahThen, we haveProducing Nonnegative Weights 0-40-523451-4376214-18-5000000s0-40-52345104102200-1130510400s( , )( , )( )( )w u vw u vh uh vh vs v( )( , )Johnsons algorithm1. Find a vertex labeling h such that (u, v

3、) 0 for all (u, v) E by using Bellman-Ford to solve the difference constraints h(v) h(u) w(u, v), or determine that a negative-weight cycle exists.Time = O(VE). 2. Run Dijkstras algorithm from each vertex using .Time = O(VE + V2 lg V).3. Reweight each shortest-path length (p) to produce the shortest

4、-path lengths w(p) of the original graph.Time = O(V2). Total time = O(VE + V2 lg V).Johnsons algorithm Johnsons 演算法利用reweighing來除去負邊，使得該圖可以套用Dijkstra演算法，來達到較高的效能。 Reweighing是將每個點v設定一個高度h(v)，並且調整邊的weight function w(u,v)成為w(u,v)=w(u,v)+h(u)-h(v)。 令(u,v)如此調整之後的最短距離，則原先的最短距離(u,v)=(u,v)-h(u)+h(v)。Johnson

5、s algorithmJohnson(G) compute G, where VG=VG s and EG=EG (s,v):v VGif Bellman-Ford(G,w,s)=False then print “ a neg-weight cycle”else for each vertex v VG set h(v)= (s,v) computed by Bellman-Ford algo. for each edge (u,v) EG w(u,v)=w(u,v)+h(u)-h(v) for each vertex u VG run Dijkstra(G,w,u) to compute

6、(u,v) for each v VG duv= (u,v)-h(u)+h(v)return DJohnsons algorithm範例範例37428-461-5Johnsons algorithm範例範例37428-461-5s00000加入一個點s，以及自s拉一條weight為0的邊到每一點。Johnsons algorithm範例範例-10-5-4037428-461-5s00000執行Bellman-Ford演算法，得到自s出發每一點的最短距離。Johnsons algorithm範例範例-10-5-4041002130200做完reweightingJohnsons algorith

7、m範例範例2/10/02/-30/-42/241002130200紅線部分是Shortest-paths tree。點的數字a/b代表自出發點(綠色點)出發，到達該點的最短路徑(Reweighting後的圖/原圖)。Johnsons algorithm範例範例0/02/30/-42/-10/141002130200Johnsons algorithm範例範例0/42/70/02/30/541002130200Johnsons algorithm範例範例0/-12/20/-52/-20/041002130200Johnsons algorithm範例範例2/54/82/10/02/641002130200Johnsons algorithm複雜度分複雜度分析析 執行一次Bellman-Ford。O(|V|E|)。 執