この記事は、コース「アルゴリズムとデータ構造」の開始前夜に作成されました。
ジョンソンのアルゴリズムは、負の輪郭のない負の重みを持つ加重有向グラフ内の頂点のすべてのペア間の最短パスを見つけます。
ああ、なんて聞こえるんだ！問題の説明を部分的に分析してみましょう。
, , ( – ), . , 4 8 :
. «» «».
, «» «» . , . – . , D , .
, , , . . . «» «», , , .
, , , :
.
-, « » :
for k = 1 to n // n –
for x = 1 to n
for y = 1 to n
W[x][y] = min(W[x][y], W[x][k] + W[k][y]) W[x][y] .
W – . , .
«» . X Y , – .
- , – , – .
. , , , -.
, .
, , (-2), «» D (-2+6=4). . CD .
. , .
?
: ! : , , . !
?
– , . ? , .
, 4, A D : 5 + 1 * 4 = 9. 3 (A-B-C-D) 12 : -2 + 8 – 4 + 3 * 4 = 14.
, – , . ? XY h(X) h(Y), h(v) – «» , .
:
 |
|
 |
|---|
, A D:
, A D , h(A) – h(D), , , ! , .
h, .
,
- S, . , S S* , S, «» .
-, S . N «» S . «» , , :
h . – S. S , h – . , , , , , , :
:
, , , ! .
, :
, , , . . , A D : A <= B <= C <= D, .
, . , .