Нахождение кратчайшего пути.
Пусть задан ориентированный граф G=(V,E), у которого все дуги имеют неотрицательные метки – стоимости дуг, одна из вершин - i0 - определена как источник. Стоимость пути определяется как сумма стоимостей входящих в него дуг. Под длиной пути в данной задаче будем понимать его стоимость.
Задача состоит в нахождении путей минимальной стоимости от вершины-источника до всех остальных вершин. Для решения этой задачи обычно применяется алгоритм Дейкстры или алгоритм Флойда.
Алгоритм Дейкстры.
Пусть V-множество всех вершин графа, S – множество вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для всех остальных вершин. Введём понятие ‘Особый путь’. Особый путь до вершины k, принадлежащей S, – это путь от вершины-источника до вершины k, проходящий только через вершины из S и вершину k.
Пример:
Кратчайший особый путь до вершины 4 – это путь 1-2-4 стоимостью 210. Есть и более дешевый путь 1-5-4, но он не является особым, так как 5 не принадлежит S.
Создадим массив D, где D
– длина кратчайшего особого пути до вершины i. На каждом шаге алгоритма значения в D корректируются. По завершении работы алгоритма массив D будет содержать длины кратчайших путей к каждой вершине.
Алгоритм Дейкстры выглядит следующим образом:
Пусть стоимости дуг хранятся в массиве C, C[i,j] - cтоимость дуги из вершины i в вершину j. Если такой дуги не существует, то положим C[i,j]:=? (при программировании можно использовать просто большое число).
[code]
S := {i0};
for i:=1 to n do D := С[i0,i]; {первоначально особые пути – просто длины дуг от вершины-источника}
for i:=1 to n-1 do begin
выбрать из множества VS такую вершину w, что значение D[w] минимально. (*)
S:=S+[w];
{множество S изменилось – корректируем длины кратчайших особых путей в массиве D}
for каждая вершина v из множества VS do
D[v]:=min(D[v], D[w]+C[w,v]); (**)
end;
[/code]
Рассмотрим подробнее строку (**). В ней корректируется длины кратчайших особых путей до оставшихся вершин v после добавления вершины w в множество S. Кратчайший особый путь до v либо будет проходить через w, либо нет.
Если нет, то он останется без изменения (а с чего бы ему тогда измениться?) и его длина останется D[v].
Если да, то он будет выглядеть так: 1-…-w-v, и его длина найдётся как сумма длины кратчайшего пути от 1 до w (т.е. D[w]) и длины дуги w-v, т.е. C[w,v].
Рассмотрим пример.
Номер вершины-источника – 1.
Таким образом, мы определили длины кратчайших путей. Вопрос в следующем – как найти сами эти пути?
Для этого внесём небольшие дополнения в алгоритм.
Введём массив P, где P[v] содержит вершину, непосредственно предшествующую вершине v в кратчайшем пути. Вначале положим P[v]=i0 для всех v, не равных i0.
Вместо (**) запишем следующее:
[code]
if D[w]+C[w,v]
Время выполнения алгоритма Дейкстры.
Пусть орграф имеет n вершин и e дуг, граф представлен матрицей смежности. Тогда для выполнения цикла в строке (*) потребуется время порядка O(n2).
Если количество дуг k значительно меньше n*n, то граф лучше всего представлять с помощью списков смежности, а множество VS – с помощью очереди с приоритетами, реализованной с помощью частично упорядоченного дерева. В этом случае (*) потребует время O(log n), а (**) – O(k*log n). Т.о. общее время O(k*log n), что значительно меньше O(n2), когда k существенно меньше n2.
Реализацию алгоритма можно найти на форуме, в разделе про олимпиадные задачи
(в задаче "Сеть " используется алгоритм Дейкстры с крохотными непринципиальными изменениями):
[url=http://forum.excode.ru/viewtopic.php?id=237 url][/url]
