具有负弧的有向图上的Johnson算法

本文是在“算法和数据结构”课程开始的前夕编写的

---

约翰逊算法在具有负权重而没有负轮廓的加权有向图中找到所有顶点对之间的最短路径。

哦，听起来如何！让我们分部分分析问题陈述。

, , ( – ), . , 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, .

, . , .

---

« »

---