[アルゴリズム]25.すべてのペアの最短パス
952 ワード
allpairはsingle-sourceを|V|に回転させると現れ、これよりも良い方法で得られる.ここでは隣接行列を用いて表す
wij = i=j : 0
i != j,実際の幹線:その重量
実際の幹線ではなく違う:無限大
Dynamic programming algorithm :
1.最適解構造の定義
2.そのソリューションの再定義
3.bottomupで解く
4.最適解を見つける
structure of shortest path
最短パスのサブセクションはすべて最短パスです.
->wijでi=jの場合、wは0/i!=jがkを経て2つの経路を統合すると仮定する
recursive solution to all pairs shortest paths problems
computing the shortest path weights bottom up
Extend-Shortest-Path(L,W)
n = L.rows
let L' = (l'ij) be a new nxm matrix
for i =1 to n
for j =1 to n
l'ij =무한
for k =1 to n
l'ij = min(l'ij, lik+wkj)
Slow-All-Pairs-Shortest-Paths(W)
n = W.rows
L(1) = W
for m =2 to n-1
let L(m) new nXn matrix
L(m) = Extend-Shortest-Path(L(m-1), W)
return L(n-1)Reference
この問題について([アルゴリズム]25.すべてのペアの最短パス), 我々は、より多くの情報をここで見つけました https://velog.io/@rkdud007/알고리즘-25.-모든쌍의-최단경로テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol