Теперь сделаем индуктивный шаг. Уже проделано s общих шагов, уже С’={, , , …, }, при этом все кратчайшие пути из в v’ не содержат вершин из С в качестве промежуточных.

Найдем минимальное Len[l] в неотмеченных столбцах; пусть минимум достигается на вершине . Соответственный элемент , меняясь, мог принимать только номера отмеченных вершин, значит в вершину идет путь, где все вершины, кроме конечной , – штрихованные, т.е. принадлежащие С’. Любой другой путь [… ], содержащий хотя бы еще одну не штрихованную вершину, будет длиннее. Теорема доказана.

Uses Crt;

Const MaxSize=10;

Infinity=1000;

Var Mattr: array [1 MaxSize, 1 MaxSize] of integer;

Visited: array [1 MaxSize] of boolean;

Len,Path: array [1 MaxSize] of integer;

n, Start, Finish, k, i: integer;

Procedure Init;

Var f: text;

i, j: integer;

Begin

Assign(f, INPUT.MTR');

Reset(f);

Readln(f, n);

For i:=1 to n do

Begin

For j:=1 to n do Read(f, mattr[i,j]);

Readln(f)

End;

Write('Начальная вершина: '); Readln(Start);

For i:=1 to n do

Begin

Visited[i]:=False;

Len[i]:=Mattr[Start, i];

Path[i]:=Start

End;

Path[Start]:=0;

Visited[Start]:=True

End;

Function Possible: Boolean;

Var i: integer;

Begin

Possible:=True;

For i:=1 to n do If not Visited[i] then Exit;

Possible:=False

End;

Function Min: Integer;

Var i, minvalue, currentmin: integer;

Begin

Minvalue:=Infinity;

For i:=1 to n do

If not Visited[i] then

If Len[i]<minvalue then

Begin

currentmin:=i;

minvalue:=Len[i]

End;

min:=currentmin

End;

Begin

ClrScr;

Init;

While Possible do

Begin

k:=min;

Visited[k]:=True;

For i:=1 to n do

If Len[i]>Len[k]+Mattr[i, k] then

Begin

Len[i]:=Len[k]+Mattr[i, k];

Path[i]:=k

End

End;

Write('Конечная вершина: '); Readln(Finish);

Write(Finish);

Finish:=Path[Finish];

While Finish<>0 do

Begin

Write('<-', Finish);

Finish:=Path[Finish];

End;

ReadKey

End.

Например, для сети, описанной в предыдущей главе, кратчайший путь из 3-ей вершины в 8-ю будет: 8¬2¬3.