Кратчайшие пути

Ранее уже была рассмотрена задача о кратчайших путях, для решения которой можно применять метод поиска в ширину. В той задаче под длиной пути понималось число ребер в нем, т.е. все ребра считались имеющими одну и ту же единичную длину. Теперь рассмотрим более общую задачу, в которой длины ребер могут быть различными. Предполагаем, что задан связный граф и для каждого его ребра указана длина этого ребра – неотрицательное число. Длина пути есть сумма длин его ребер.

Рассмотрим задачу отыскания путей наименьшей длины от заданной вершины a до всех остальных вершин графа. Возможно, более естественной постановкой задачи кажется поиск кратчайшего пути между двумя заданными вершинами. Однако в настоящее время не известно никакого способа решения этой задачи, существенно лучшего, чем поиск кратчайших путей от начальной вершины до всех остальных. Наиболее известным способом решения этой задачи является описываемый далее алгоритм Дейкстры (E. Dijkstra).

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

Алгоритм Дейкстры очень похож на алгоритм Прима. В нем процесс построения дерева тоже начинается с одной вершины, только в алгоритме Прима это могла быть любая вершина графа, а теперь это должна быть вершина а. В дальнейшем на каждом шаге к дереву присоединяется одно новое ребро (и одна вершина). Это ребро выбирается из подходящих ребер, причем понятие подходящего ребра здесь такое же – это ребро, соединяющее вершину дерева с вершиной, ему не принадлежащей. И правило выбора добавляемого ребра такое же – среди подходящих ребер выбирается ребро наименьшего веса. Разница в том, что в алгоритме Прима веса ребер заданы изначально, а в алгоритме Дейкстры они вычисляются.

Пусть – частичное дерево кратчайших путей, построенное к некоторому моменту. Обозначим через длину пути между вершинами х и а в дереве Т. В качестве веса подходящего ребра принимается величина .

Теорема об алгоритме Дейкстры. Дерево, построенное с помощью алгоритма Дейкстры, является деревом кратчайших путей.

Алгоритм Дейкстры для ускорения работы модифицируется так же, как алгоритм Прима. Распространим определение функции L на множество : для положим равным наименьшему значению величины по всем . Через обозначим то значение z, на котором этот минимум достигается. Таким образом, – это длина кратчайшего пути из а в y, проходящего только через вершины множества U (кроме вершины y), а ­– предпоследняя вершина этого пути. Теперь алгоритм Дейкстры можно записать следующим образом.