Второй этап.. Первый этап.

⇐ ПредыдущаяСтр 5 из 5

Второй этап.

Если W(t)<M, то выполняем второй этап алгоритма Беллмана-Калабы, в противном случае задача решения не имеет.

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 считаем временной помеченной вершиной для всех iÎE\{t} W(i):=M, вершины iÎE\{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-й шаг. Среди vÎV ⁺(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,

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

⇐ Предыдущая 1 2 3 45