Замечание
Поскольку данный алгоритм является эвристическим, найденное решение будет зависеть от выбора начальной вершины. Например, если выбрать начальную вершину b, то алгоритм дает следующее решение:
Алгоритм нахождения нижней границы проблемы путешествующего купца:
Выбрать у взвешенного полносвязного графа вершину VSи удалить её из графа вместе с инцидентными к ней рёбрами.
Найти минимальное каркасное дерево T, соединяющее оставшиеся вершины и подсчитать общий вес дереваw(для этой цели использовать алгоритм Крускала или метод Прима).
Найти два наименьших веса, w1 и w2, рёбер, инцидентных сVS. Тогдаw+w1+w2является нижней границей решения проблемы путешествующего купца.
Пример
a a
7
1
d
Находим минимальное каркасное дерево Т:
Два ребра с наименьшими весами, инцидентные вершине а:
w1=w(a,e)=2,
w2 =w(a,c)=4.
5. Нижняя граница решения проблемы ТСР
w+ w1+ w2=16+2+4=22.
Замечание
Как и для случая оценки верхней границы, величина оценки нижней границы зависит от выбора вершины VS. Например, если взятьVS=d, то получим:
Это решение замечательно тем, что верхняя и нижняя границы совпали! Следовательно, точное решение проблемы ТСР=26.
Кратчайшие пути во взвешенных
графах и орграфах
Определения
Задан граф G=(V,E) или орграфD=(V,A) с функцией весаw:E→R(илиw:A→R).
Вес w(P) пути
P=(v0,e0,v1,e1,…,vk-1,ek-1,vk)
Определяется как сумма весов ребер (дуг) пути:
w(P)=w(ei).
Путь между вершинами uиvбудеткратчайшим (минимальным), если его вес будет наименьшим по сравнению с другими возможными путями между этими вершинами:
δ(u,v)= minwi(u,v).
Существуют следующие разновидности зазачи определения кратчашего пути графа (орграфа):
Задача простой пары (Simple Pair Problem)– задан граф (орграф) и вершиныu,vV. Найти кратчайший путьw(P).
Задача одного источника (Single Source Problem) - задан граф (орграф) и вершиныsV. Вершинаsназываетсяисточником. Найти кратчайшие пути от источникаsко всем остальным вершинам.
Задача всех пар (All Pairs Problem)– найти кратчайшие расстояния между всеми возможными парами вершин графа (орграфа).
Класс сложности
Проблема нахождения кратчайших путей в графе (орграфе) относится к Р-классу (полиномиальному классу).
Алгоритм Дейкстры (Dijkstra)
Является алгоритмом решения задачи одного источника графа и орграфа при неотрицательных весах ребер (дуг).
Атрибуты
В графе G=(V,E) задана вершина-источникs. Для каждой вершиныvVустанавливаюся следующиеатрибуты:
d[v] –верхняя граница весакратчайшего пути междуsиr;
π[u] –вершина-предшественник: вершинаuявляется последней вершиной, из которой путь пришел в вершинуv;
stat[v] – статус вершины. Имеет три значения: {недостигнута, помечена, просмотрена}.
Релаксация
Процесс релаксации ребра {u,v} позволяет определить, уменьшается ли кратчайший путь при добавлении в этот путь какого-либо ребра.
Пусть d[v] будет оценкой кратчайшего расстояния от вершиныsк вершинеv, полученная ранее. Предшественником вершиныvбыла вершинаz, т.е.π[z]=v. При добавлении к пути между s и v нового ребра {u,v} возможны два варианта (далееw(u,v) обозначает вес ребра {u,v}):
d[v]<d[u]+w(u,v). В этом случае оценка расстояния d[v] остается неизменной.
d[v]>d[u]+w(u,v). В этом случае надо изменить атрибутd[v]=d[u]+w(u,v) и указать предшественника вершины v – π[v]=u.
Механизм релаксации ребер лежит в основе почти всех алгоритмов нахождения кратчайших путей.
Пример
s
“Cтарый”
путь Оценки кратчайшего
пути: -d[v]=9
при предшественнике π[v]=x; -d[u]=5.
x
Изменненый путь
v u 2
При новой итерации
алгоритма путь к вершине vполучается добавление ребра {u,v}. Тогда d[v]=9<d[u]=5+w(u,v)=2=7. Релаксация ребра: d[v]=7,π[v]=u.
Инициализация:
d[s]=0, stat[s] =просмотрена,
d[v]=,
vV-s,
π[v]=nil,
stat[v]=недостигнута
для всех вершинvV-s.
Создать приоритетную очередь
Q вершин.
До тех
пор, пока Qне будет пуста,
делать:
{изять вершину uиз головы очередиQ;
{для каждой вершины
z, инцидентной вершинеu,
делать
{ если d[z]>d[u]+w(u,z),
тогда
d[z]=d[u]+w(u,z);
stat[z]=помечена;
stat[u]=просмотрена;
π[z]=u.
Убрать uиз очереди, поставитьzв очередь
}
}
Существует несколько способов создания приоритетной очереди. Самым простым явялется метод сортировки: очередь сортируется по созрастанию d[v] – от меньшего (голова очереди) к наибольшему (хвост очереди). Еслиd[v]=d[u], то размещение ребер в очереди друг относительно друга несущественно.
В этом случае сложность алгоритма O(n2+m), гдеn=|V|,m=|E|.
По указателям-предшественникам восстанавливаются кратчайшие пути (записываются только вершины пути)
d[s]=0;
π[b]=s → (s-a), d[a]=3 π[c]=d, π[d]=b, π[b]=s → (s-b-d-s), d[c]=7
π[d]=b, π[b]=s → (s-b-d), d[d]=4 π[e]=d, π[d]=b, π[b]=s → (s-b-d-e), d[e]=7.