Алгоритм фронта волны. Поиск минимального пути в графе.

 

Одной из самых распространенных задач в теории графов является задача поиска минимального пути в графе.

Рассмотрим некоторые свойства минимальных путей

1. Любой минимальный путь является простым путем.

2. Если путь - минимальный, то любые пути внутри минимального пути также будут минимальны.

Пусть Г^-1_х – прообраз вершины x_i – это множество вершин, из которых исходят дуги в вершину x_i.

Одним из алгоритмов поиска минимального пути в графе является алгоритм фронта волны (FW –Front Wave)