- •6.1. Транспортная задача в сетевой постановке
- •6.2. Критерий оптимальности
- •6.3. Алгоритм поиска исходного базисного дерева
- •7.1. Задача о максимальном потоке в сети
- •7.2. Решение задачи о нахождении кратчайших расстояний на графе между двумя вершинами алгоритмами Беллмана-Калабы, Флойда, Дейкстры
- •7.3. Алгоритм Беллмана-Калабы для отыскания кратчайших расстояний на графе между двумя вершинами
- •7.4. Алгоритм Флойда для отыскания кратчайших расстояний на графе
- •7.5. Алгоритм Дейкстры отыскания кратчайших расстояний на графе
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,
являющееся решением задачи.
