Компьютерные сети. Лабораторные работы



Система дорог - часть 2


{ Помещение Elem в стек Stack }

var q: svqz;

BEGIN

New (q); q^.Element:=Elem; q^.Sled:=Stack; Stack:=q

END;

{ --- }

BEGIN

{ Ввод матрицы весов дуг заданного графа }

WriteLn ('Вводите элементы матрицы весов дуг по стро-кам :');

For i:=1 to MaxNodes do

For j:=1 to MaxNodes do

begin

Write (' Введите A[',i,',',j,']: ');

ReadLn (A[i,j]);

If A[i,j]=0 then A[i,j]:=B

end ;

Write ('Введите источник: '); ReadLn ( S );

{ Инициализация }

For i:=1 to MaxNodes do D[i]:=A[S,i];

D[S]:=0;

{ Вычисление матрицы расстояний от источника до всех вершин графа }

For k:=1 to MaxNodes-2 do

For i:=1 to MaxNodes do

If i<>S

then For j:=1 to MaxNodes do

If D[i]>D[j]+A[j,i] then D[i]:=D[j]+A[j,i];

{ Вывод матрицы расстояний от источника до всех вершин графа }

WriteLn (' Матрица расстояний : ');

For i:=1 to MaxNodes do Write (D[i],' ');

WriteLn ;

{ Нахождение кратчайшего пути из S в T с помощью }

{ построенной матрицы расстояний }

Write ('Введите конечную вершину пути: '); ReadLn (T);

Stack:=Nil; V__S_t_a_c_k (Stack,T); v:=T;

While v<>S do

begin

For i:=1 to MaxNodes do

If D[v]=D[i]+A[i,v] then u:=i;

V__S_t_a_c_k (Stack,u); v:=u

end ;

{ Вывод кратчайшего пути на экран дисплея }

Write ('Кратчайший путь: '); UkZv:=Stack ;

While UkZv<>Nil do

begin Write (UkZv^.Element,' '); UkZv:=UkZv^.Sled end;

WriteLn

END.

Рассмотрим тестовый пример [Евстигнеев,Мельников,1981]. Вычислить кратчайшее расстояние между вершинами s и t в сети:

(s,a,4), (s,d,6), (a,d,-3), (a,b,8), (b,t,2), (a,e,5),

(d,e,2), (e,c,3), (d,c,11), (c,b,-4), (c,t,7), (b,d,-6).

Перенумеруем вершины следующим образом:

(s,1), (a,2), (d,3), (b,4), (c,5), (e,6), (t,7),

а затем выпишем матрицу весов дуг

и применим алгоритм Форда-Беллмана к этой матрице. В результате получим:

Введите источник: 1

Матрица расстояний: 0 4 -4 2 1 -2 4

Введите конечную вершину пути: 7

Кратчайший путь: ...

Компьютер "зависает", ибо в графе имеется контур отрицательной длины 3-6-5-4 (его длина -6+2+3-4=-5), что приводит к появлению бесконечного множества путей, каждый из которых "короче" предыдущего, например:




Содержание  Назад  Вперед