Задача о кратчайшем пути

 

Исторически сложились три задачи о поиске пути в графе.

Задача 1. Найти любой путь (цепь) из А в В.

Задача 2. Найти кратчайший путь из А в В в смысле количества ребер (дуг).

Алгоритм решения задачи о нахождении кратчайшего пути из А в В в смысле наименьшего количества ребер:

1. Вершине А припишем индекс 0.

2. Всем вершинам, смежным с А, припишем индекс 1.

3. Всем вершинам, смежным с вершинами индекса 1 и не имеющим индекса, припишем индекс 2 и т.д.

4. Как только вершина В получит некоторый индекс, процесс присвоения останавливается. Значение индекса n вершины В и есть длина кратчайшего пути из А в В. Построим этот путь.

5. Среди вершин, смежных с В, обязательно найдется вершина с индексом n-1 (одна или несколько), возвращаемся в эту вершину и продолжаем этот процесс.

6. Через n шагов придем в вершину с индексом 0, т.е. в А. Один или несколько путей построены.

Если каждому ребру (дуге) графа приписано некоторое число l_k³0 (вес ребра), то граф называется взвешенным (нагруженным)

Задача 3. Найти кратчайший путь из А в В во взвешенном графе (в смысле суммы весов ребер (дуг)).

Приведем алгоритм решения задачи 3.

Будем постепенно приписывать всем вершинам графа числовые индексы:

1. Вершине А припишем индекс 0, всем остальным вершинам значение +¥.

2. Будем постепенно перебирать все пары смежных вершин v_x и v_y. Каждый раз проверим первенство , если оно

3.

vy

выполняется, то уменьшаем индекс , заменив его на .

 

vx

 

4. Процесс останавливаем, когда ни один индекс уже нельзя уменьшить. В этот момент вершина В имеет некий индекс m. Это и есть наименьшая сумма весов всех дуг.

5. Построим путь с такой суммой. Будем возвращаться из вершины В в А. Среди вершин, смежных с В, обязательно найдется вершина С, для которой выполняется точно равенство m_В=m_С+l_СВ.

Возвращаемся к С и повторяем процесс. Поскольку индексы все время уменьшаются, то через несколько шагов придем в вершину с индексом 0, т.е. вершину А.