Алгоpитм Дейкстpа
- From
- Alex Lisenko (2:465/4.8)
- To
- Vladislav Irdullin
- Date
- 2000-02-27T15:02:07Z
- Area
- RU.ALGORITHMS
Здравствуй Vladislav!
Среда апрель 02 2036, а Vladislav Irdullin пишет All вот что:
VI> Объясните, кто может, пpинцип алгоpитма Дейкстpа (не увеpен в пpавильности
VI> написания фамилии) для нахождения кpатчайшего пути в гpафе.
Вот.
>--- Begin [DEIKSTRA.ALG] ---<
Обозначения:
C[i,j]- длина ребра(i,j), С[i,j]>=0 (если ребра нет, то его
длина полагается равной бесконечности).
D[i]- кратчайшее текущее расстояние от вершины нач до вершины i.
флаг[i]- информация о просмотре вершины i: 0 - если вершина
не просмотрена, 1 - если просмотрена. Если вершина просмотрена, то
для нее D[i] есть наикратчайшее расстояние от вершины нач до вер-
шины i.
предок[i]- информация о номере вершины, предшествующей верши-
не i в кратчайшем пути от вершины нач.
минрас - это минимальное расстояние.
Алгоритм:
для i от 1 до N выполнять
нц
предок[i]:=нач;
флаг[i]:=0;
D[i]:=C[нач,i]
кц
флаг[нач]:=1; { пока мы знаем только расстояние }
предок[нач]:=0 { от вершины нач до нее же, равное 0 }
для i от 1 до N-1 выполнять
нц
минрас:=бесконечность;
для j от 1 до N выполнять
если (флаг[j]=0 и (минрас > D[j]) { находим минимальное}
то минрас:=D[j]; {расстояние}
k:=j; { до непомеченных вершин }
все
флаг[k]:=1; { вершина k помечается просмотренной }
для j от 1 до N выполнять { выполняем просмотр }
если флаг[j]=0 и D[j]>D[k]+C[k,j]
{ Т.е. если для вершины j еще не найдено кратчайшее
расстояние от нач, и из вершины k по дуге C[k,j]
путь в j короче, чем найденный ранее }
то D[j]:=D[k]+C[k,j] { то запоминаем его }
предок[j]:=k;
все
кц
>--- End [DEIKSTRA.ALG] ---<
Всего хорошего,
Alex Lisenko.
---
* Origin: Origin sugarfree! (2:465/4.8)