Определение: Путь (маршрут) в орграфе Д (графе G) из вершины vi в вершину vj (i j) называется минимальным, если он имеет минимальную длину среди всех путей (маршрутов) орграфа Д (графа G).
Алгоритм поиска минимального пути из v в w орграфе Д (графе G).
Введем обозначения: Пусть Д = (V, X) – орграф, v V, V1 V
Обозначим
Д(v) = {w V | (v,w) X} – образ вершины v
Д-1(v) = {w V | (w, v) X} – прообраз вершины v
Д(V1) = Д(v), где v V1 – образ множества вершин V1.
Д-1(V1) = Д-1(v), где v V1 – прообраз множества вершин V1.
Пусть G = (V, X) – граф, v V, V1 V
Обозначим
G(v) = {w V | (v,w) X} – образ вершины v
G(V1) = G(v), где v V1 – образ множества вершин V1
Пусть Д = (V, X) – орграф с n вершинами (n 2).
v, w – заданные вершины из V, vw.
Опишем алгоритм поиска минимального пути из v в w в орграфе Д (алгоритм фронта волны).
1. Помечаем вершину v индексом 0, т. е. F W0 (v) = { v }. Затем помечаем образы вершины v, индексом 1. Множество вершин с индексом 1 обозначим FW1(v). Полагаем k = 1.
2. Если FWk(v) = Ø или k = n – 1, w FWk(v), то вершина w не достижима из вершины v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.
3. Если w FWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины k и этот путь минимальный.
Последовательность вершин:
v w1w2 … wk-1w, где
wk-1 F Wk-1 (v) ∩ Д-1 (w) (1)
wk-2 F Wk-2 (v) ∩ Д-1 (wk-1)
…
w1 F W1 (v) ∩ Д-1 (w2)
и есть искомый путь длины k из v в w. На этом работа алгоритма заканчивается.
4. Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k+1 обозначаем F Wk+1 (v). Присваиваем k := k+1 и переходим к шагу 2.
Множество F W(v) в алгоритме обычно называют фронтом волны k-гоуровня.
Вершины w1, …, wk-1 из последовательности (1), вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных минимальных путей из v в w.