В задаче о кратчайшем пути (shortest-paths problem) задается взвешенный ориентированный граф G = (V, Е) с весовой функцией w : Е —> R, отображающей ребра на их веса, значения которых выражаются действительными числами. Вес (weight) пути р = (Vo, Vi,..., Vk) равен суммарному весу входящих в него ребер.

Вес кратчайшего пути (shortest-path weight) из вершины и в вершину v определяется соотношением

Тогда по определению кратчайший путь (shortest path) из вершины и в вершину v — это любой путь, вес которого удовлетворяет соотношению w (р) = delta(u, v).

Вес каждого из ребер можно интерпретировать не как расстояние, а как другую метрику. Часто они используются для представления временных интервалов, стоимости, штрафов, убытков или любой другой величины, которая линейно накапливается по мере продвижения вдоль ребер графа и которую нужно свести к минимуму.

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

1) Задача о кратчайшем пути в заданный пункт назначения (single-destination shortest-paths problem). Требуется найти кратчайший путь в заданную вершину назначения (destination vertex) t, который начинается в каждой из вершин v. Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине.

2) Задача о кратчайшем пути между заданной парой вершин (single-pair shortest-paths problem). Требуется найти кратчайший путь из заданной вершины u в заданную вершину v. Если решена задача о заданной исходной вершине u, то эта задача тоже решается.

3) Задача о кратчайшем пути между всеми парами вершин (all-pairs shortest-paths problem). Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.

В данном разделе представлен алгоритм Беллмана-Форда, позволяющий решить задачу о кратчайшем пути из фиксированного истока в общем случае, когда вес любого ребра может быть отрицательным. Этот алгоритм отличается своей простотой. К его достоинствам также относится то, что он определяет, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Также в разделе описывается алгоритм Дейкстры, который характеризуется меньшим временем выполнения, чем алгоритм Беллмана-Форда, но требует, чтобы вес каждого из ребер был неотрицательным. Кроме того, приведен алгоритм динамического программирования — алгоритм Флойда-Варшалла (Floyd-Warshall), который позволяет решить задачу о поиске кратчайших путей между всеми парами вершин.

[вверх]