Re: Алгоpитм Дейкстpа
- From
- Andrey Popov ()
- To
- All ()
- Date
- 2000-02-25T07:12:25Z
- Area
- RU.ALGORITHMS
From: "Andrey Popov" <andrewp@asuneft.ru>
Vladislav Irdullin <Vladislav.Irdullin@p111.f21.n5093.z2.fidonet.org>
сообщил в новостях следующее:951419495@p111.f21.n5093.z2.ftn...
> ·--------·==│
│==·--------·
> │ Пpивет, All !
> │
>
>
> Объясните, кто может, пpинцип алгоpитма Дейкстpа (не увеpен в пpавильности
> написания фамилии) для нахождения кpатчайшего пути в гpафе.
>
> │ Пока, All !
> │ Vladislav 333:1/286.111@hacknet
> ----------· ·-----------
>
Привет!
Алгоритм Дейкстры предназначен для нахождения кратчайшего пути во взвешенном
графе, причем все веса должны быть неотрицательными (иначе метод не
годится).
Пусть нам требуется найти кратчайший путь (путь минимальной стоимости) из
вершины А в вершину В). Пусть для каждого ребра заданы стоимости (веса) С_i.
Каждой вершине сопоставляем два числа: P_j и Pred_j (номер вершины, из
которой мы пришли в данную).
1. Первоначально вершина А помечается 0 (P_A=0), для всех остальных пометка
= бесконечности.
2. Затем находим все вершины, смежные с А, и высчитываем для них пометки по
правилу:
P_j=P_A+C_i, где С_i - стоимость ребра, соединяющего вершины А и j. Если
высчитанная пометка меньше, чем та, которая была у j-ой вершины, то меняем
пометку и запоминаем в значении Pred_j номер вершины, из которой пришли в
вершину j ( в данном случае А).
3. Теперь полагаем А=j и переходим к пункту 2, пока не достигнем вершины В.
После работы алгоритма значение P_B будет равно стоимости минимального пути,
а Pred_B - номеру вершину, по которой пришли в В. Переходим в эту вершину
(k), смотрим
значение Pred_k ( номер вершины, из которой пришли в вершину k) и т.д. Так
последовательно восстанавливаем путь из В в А.
Буквально вчера написал процедуру Pometki, которая как раз и находит
кратчайший путь из одной вершины в другую (дерево у меня не взвешенное,
поэтому я полагал, что веса для каждого ребра равны 1). По-моему, процедура
работаем правильно. Привожу ее текст ниже.
TPometka = record
Ves: LongInt;
Prev: LongInt;
end;
var Pometki:array of TPometka;
{ Помечает смежные с данной вершины, пропуская данное ребро, здесь нам
надо найти путь из NodeIndex в IndexTo. PipeIndex - номер ребра, по
которому пришли в NodeIndex }
procedure Adjacents(NodeIndex,PipeIndex:LongInt);
{Граф хранится как массив ребер MyGraph[], Для каждого ребра определено поле
BeginIndex, EndIndex - индексы начальной и конечной вершины графа в массиве
вершин}
var
j,NextIndex:LongInt;
Begin
if NodeIndex=IndexTo then exit;
For j:=0 to PipesCount-1 do begin
NextIndex:=-1;
{ Находим ребро, инцидентное данной вершине и не совпадающее
с заданным }
if (MyGraph[j].BeginIndex=NodeIndex) and (PipeIndex<>j) then
NextIndex:=MyGraph[j].EndIndex;
if (MyGraph[j].EndIndex=NodeIndex) and (PipeIndex<>j) then
NextIndex:=MyGraph[j].BeginIndex;
{ Изменяем пометки, если это необходимо }
If NextIndex>-1 then
{ Переходим от этой вершины к следующей только если это улучшает пометки }
{ Если веса не равны все 1, то прибовлять надо не 1, а вес данного ребра }
if (Pometki[NextIndex].Ves>Pometki[NodeIndex].Ves+1) or
(NextIndex=IndexTo) then begin
Pometki[NextIndex].Ves:=Pometki[NodeIndex].Ves+1;
Pometki[NextIndex].Prev:=NodeIndex;
{ Рекурсивный переход }
Adjacents(NextIndex,j);
end;
end;
end;
Осталось по пометкам восстановить кратчайший путь.
Если будут вопросы, пиши. Пока.
С уважением, Андрей Попов.
email: andrewp@asuneft.ru
--- ifmail v.2.15dev4
* Origin: Nizhnevartovsk ASUNeft JSC (2:5020/400)