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



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


D[S]:=0; Q:=[];

For i:=1 to MaxNodes do Q:=Q+[i];

Q:=Q-[S];

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

While Q<>[] do

begin

Min:=B;

For i:=1 to MaxNodes do

If (i IN Q) AND (D[i]<Min)

then begin Min:=D[i]; u:=i end;

Q:=Q-[u];

For i:=1 to MaxNodes do

If i IN Q

then If D[i]>D[u]+A[u,i]

then D[i]:=D[u]+A[u,i]

end ;

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

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 1 2 6 3 4

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

Кратчайший путь: 1 2 3 6 5 4 7

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

путь 1-2-3-6-5-4-7 с длиной 4,

путь 1-2-3-6-5-4-3-6-5-4-7 с длиной -1,

путь 1-2-3-6-5-4-3-6-5-4-3-6-5-4-7 с длиной -6 и т.д.

Таким образом, кратчайший путь алгоритмом Дейкстры определить нельзя, так как в графе имеется контур отрицательной длины.




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