Задачи с одним источником
Задачи с одним источником
Во многих приложениях достаточно находить кратчайшие пути только из одного узла. Такой узел называется источником.
Работа алгоритма основана на построении множества узлов S, кратчайшие расстояния до которых от источника известны. На каждом шаге к множеству S добавляется тот из оставшихся узлов, расстояние до которого от источника меньше всех других расстояний до оставшихся узлов.
Если стоимости ребер неотрицательны, то можно быть уверенным, что путь из источника в произвольный узел проходит только через узлы из множества S. Поэтому достаточно найти для каждого узла v кратчайшее расстояние до него от источника вдоль пути, проходящего только через узлы из множества S.
Алгоритм Дейкстры
Вход. Орграф G = (V, E), источник, функция l, отображающая множество V ´ V в множество неотрицательных вещественных чисел. Полагаем l(vi, vj) = +¥, если ребро не принадлежит графу, vi ¹ vj, и l(v, v) = 0.
Выход. Для каждого узла v Î V наименьшая сумма меток на ребрах, взятая по всем путям, идущим из v0 в v.
Метод. Строим такое множество узлов S Í V, что кратчайший путь из источника в каждый узел v Î S целиком лежит в S. Массив D[v] содержит стоимость текущего кратчайшего пути из v0 в v, который проходит только через узлы из S.
Рекомендуемые материалы
1. S = {v0}
2. D[v0] = 0
3. " v Î (V {v0}): D[v] = l(v0, v)
4. S ¹ V:
5. Выбрать узел w Î (V S), для которого D[w] принимает наименьшее значение.
6. Добавить w к S.
7. Для v Î (V S):
8. D[v] = MIN(D[v], D[w] + l(w, v))
Рассмотрим пример решения задачи с применением алгоритма (рис.16):
Рис.16. Граф для иллюстрации применения алгоритма Дейкстры
Результат работы алгоритма обычно оформляется в виде таблицы (табл. 1).
Таблица 1
Таблица результатов работы алгоритма Дейкстры
Итерация | S | w | D[w] | D[v1] | D[v2] | D[v3] | D[v4] |
Нач. знач. | {v0} | - | - | 2 | +¥ | +¥ | 10 |
1 | {v0 ,v1} | v1 | 2 | 2 | 5 | +¥ | 9 |
2 | {v0,v1, v2} | v2 | 5 | 2 | 5 | 9 | 9 |
3 | {v0,v1, v2, v3} | v3 | 9 | 2 | 5 | 9 | 9 |
4 | {v0,v1, v2, v3, v4} | "Спасательные плоты" - тут тоже много полезного для Вас. v4 | 9 | 2 | 5 | 9 | 9 |