Реферат: Aлгоритмы на графах

2 (общий шаг). Найти минимум среди неотмеченных (т.е. тех к, для которых Visitid[k]=False); пусть минимум достигается на индексе j, т.е. Len[j]£Len[k];

Затем выполнять следующие операции:

Visited[i]:=True;

если Len[k]>Len[j]+Matrix[j, k], то (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j)

z:=C[k];

Выдать z

z:=C[z]. Если z =0, то конец,

иначе перейти к 3.2.

Теорема. Алгоритм Дейкстры – корректен.

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);