Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Сетевые задачи экономики.doc
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
112 Кб
Скачать
☆

7.5. Алгоритм Дейкстры отыскания кратчайших расстояний на графе

Алгоритм Дейкстры применяется для случая, когда c(v)>0. В нем каждая вершина может быть:

  • непомеченной,

  • помеченной временной пометкой ,

  • помеченной постоянной пометкой.

Вершина i непомечена, если до нее не найден ни один путь из вершины t. Помечена временной пометкой, если из вершины t найден путь и величина W(i) есть верхняя оценка кратчайшего расстояния от t до i, и на последующих итерация может быть уточнена вплоть до кратчайшего расстояния от t до i. Помечена постоянной пометкой, если W(i) из верхней оценки стала кратчайшим расстоянием от t до i. Алгоритм первого этапа заканчивает работу, если W(s) стало равным кратчайшему расстоянию от t до s.

Первый этап.

0-шаг. W(t):=0; вершину t считаем временной помеченной вершиной для всех iE\{t} W(i):=M, вершины iE\{t} не помечены;

k-й шаг. Среди всех временно помеченных вершин i ищем вершину j с наименьшим значением W. Вершину j помечаем постоянной пометкой. Если j=s, то переходим к выполнению второго этапа, в противном случае просматриваем вершину j. Для этого для всех v V -(j) выполнить:

1. определяем i=h2(v).

2. если вершина i непомечена постоянной пометкой, то

W(i):=min( W(i) c(v)+W(j) ),

эта вершина помечается временной пометкой. Переходим к выполнению (k+1) шага.

Второй этап (восстановление кратчайшего пути).

0-шаг. i(0):=s;

k-й шаг. Среди vV +(i(k-1)) ищем v(k-1), для которой

W(h1(v(k)))=c(v(k))+W(i(k-1)),

i(k):=h1(v(k)).

Если i(k)=t, то алгоритм заканчивает работу, в противном случае переходим к выполнению (k+1)-го шага.

В результате выполнения второго этапа получим

t=i(k), v(k-1), i(k-1), v(k-2), ... ,v(0), i(0)=s,

являющееся решением задачи.