G = (V, ), ( ), . G. , . , ( "" , , ).
G , , v > w - v w. ̳ v > w - v w. , , v > w w > v . . , v > w w > v .
. "" , (Dijkstra).
S , . S , , , . , , S. . D, . S G, "" , D .
1. , G , V= {1, 2,..., ), 1 . C , C[i, j] i > j. i > j , C[i, j] (), - . D[i] i.
˳ 1.
procedure Dijkstra;
Begin
(1) S:= {1};
(2) for i:= 2 to n do
(3) D[i]:=C[l, i]; { D }
|
|
(4) for i:= 1 to n -1 do
Begin
(5) V\S w, D[w]
;
(6) w S;
(7) for v V\S do
(8) D[v]:= min(D[v], D([w] + C[w, v])
End
end; { Dijkstra }
, . 2.
. 2. | |||||||
S = {1}, D[2] = 10, D[3] = , D[4] = 30 D[5]= 100. ( (4) - (8) 1) w = 2, 2 D. D[3] = min(, 10 + 50) = 60; D[4] = min(30, 10 + ) = 30 D[5] = min(100, 10 + ) = 100. D :
S w D[2] D[3] D[4] D[5]
{1} | - | |||||
{1,2} | ||||||
{1, 2, 4} | ||||||
{1, 2, 4, 3} | ||||||
{1, 2, 4, 3, 5} |
: 1- , S
, ( ) - . , P[v] , v . [v] = 1 v 1. 1 (7) D[w] + C[w, v] < D[v], P[v] w. ϳ .
, . 2 : [2] = 1, [3] = 4, [4] = 1 [5] = 3. , 1 5, , 5. , 5 3, 3 - 4, , , - 1. , 1 5 : 1, 4, 3, 5.
6.2.