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

Лекция 2. Сеть. Кратчайшие пути. Алгоритм Дейкстры

Подграф, являющийся деревом и содержащий все вершины графа, называется остовным (покрывающим) деревом графа.

Эти определения иллюстрируются рис. 1.

Рис. 1. Граф G

В графе G имеется три пути между вершинами и : (), (), (). Ребра и образуют остовное дерево, то же верно для ребер и . Еще одно остовное дерево можно составить из ребер и . Вершина имеет степень 3 в графе G и степень 2 в последнем остовном дереве. Если ребро ориентировано от к , то по-прежнему есть три пути из в , но ни одного пути из в .

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

Каждой дуге сети приписано число – длина этой дуги.

В большинстве случаев длины дуг положительны, но в некоторых приложениях они могут быть и отрицательными. Например, узлы могут представлять различные состояния некоторой физической системы, а длина дуги , может означать количество энергии, поглощаемой при переходе из состояния в состояние . Отрицательная длина дуги тогда означает, что энергия излучается при переходе из в . Если суммарная длина некоторого контура или цикла в сети отрицательна, будем говорить, что сеть содержит отрицательный контур.

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

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

1) кратчайший путь от одного узла до другого;

2) кратчайшие пути от одного узла до всех других узлов;

3) кратчайшие пути между всеми парами узлов.

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

Задача нахождения кратчайшего пути корректна, если сеть не содержит отрицательного цикла (или отрицательного контура). Заметим, что сеть может иметь ориентированные дуги отрицательной длины и не иметь отрицательных циклов.

Обозначим длину дуги из в через и предположим, что

для всех i, j, (1.1)

для некоторых i, j, (1.2)

для некоторых i, j, k. (1.3)

Для удобства будем считать, что , если нет дуги из узла в узел , и для всех i.

Условие (1.3) делает задачу о кратчайшем пути нетривиальной. Если оно не выполняется, то кратчайший путь из в состоит из единственной дуги .

Обычно мы хотим знать как длину кратчайшего пути, так и последовательность его узлов. Сделаем сначала несколько замечаний. Пусть – путь из в , – промежуточный узел этого пути. Тогда подпуть от до содержит меньше дуг, чем путь . Так как длины всех дуг положительны, то этот подпуть короче, чем . Сформулируем это как замечание 1.

Замечание 1. Длина пути больше, чем длина любого его подпути. (Заметим, что это верно только если длины всех дуг положительны.)

Пусть — промежуточный узел пути (от до ). Если – кратчайший путь, то подпуть от до сам должен быть кратчайшим путем. В противном случае более короткий путь до , дополненный отрезком исходного пути от до , составил бы путь, более короткий, чем . Сформулируем это как замечание 2.

Замечание 2. Любой подпуть кратчайшего пути сам должен быть кратчайшим путем. (Заметим, что это не зависит от того, положительны ли длины дуг).

Замечание 3. Любой кратчайший путь содержит не более чем n-1 дугу. (При условии, что нет отрицательных циклов и что в сети n узлов).

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

Пусть, кратчайшие пути из во все остальные узлы упорядочены в соответствии с их длинами. Для простоты изложения мы можем переименовать узлы так, чтобы кратчайший путь в был кратчайшим среди всех кратчайших путей. Пусть пути занумерованы в порядке возрастания их длин:

.

Алгоритм найдет сначала , затем , и т.д., пока не будет найден самый длинный из кратчайших путей.

Идея алгоритма:

- Если содержал бы более одной дуги, то он выключал бы более короткий подпуть (замечание 1). Поэтому должен содержать только одну дугу.

- Если содержит более чем k дуг, то он содержит по крайней мере k промежуточных узлов. Каждый из подпутей, ведущих в промежуточный узел, короче, чем , и получается k путей, более коротких, чем , что невозможно. Поэтому кратчайший путь содержит не более k дуг. Сформулируем это как замечание 4.

Замечание 4. Кратчайший путь содержит не более k дуг.

Следовательно, чтобы найти , нужно только рассмотреть пути из одной дуги, минимальной среди них будет . Чтобы найти , нужно рассмотреть пути из одной и двух дуг. Минимальный среди них будет . Если – путь из двух дуг с последней дугой и при этом , то дуга образует подпуть , более короткий, чем . Поэтому путь должен либо состоять из одной дуги, либо из двух дуг, последней из которых является дуга .

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