Экстремальные путь на графах Задача о кратчайшем пути

Пусть задана сеть из n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины — вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети.

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

Предположим, что в сети нет контуров. Тогда всегда можно пронумеровать вершины таким образом, что для любой дуги (i, j) имеет место j > i. Такая нумерация называется правильной. В сети без контуров всегда существует правильная нумерация.

Обозначим l_ij — длину дуги (i; j). Кратчайший путь в сети, имеющей правильную нумерацию, определяется следующим алгоритмом.

Шаг 0: Помечаем нулевую вершину индексом ₀ = 0;

Шаг k: помечаем вершину k индексом .

Индекс выхода _n будет равен длине кратчайшего пути. На рисунке приведен пример применения алгоритма для определения кратчайшего пути (числа у дуг равны длинам дуг, индексы вершин помещены в квадратные скобки, кратчайший путь выделен пунктирными линиями) (рис. 2.2).

Рис. 2.2. Определения кратчайшего пути

Когда индексы (называемые в некоторых задачах потенциалами вершин) установятся, кратчайший путь определяется методом обратного хода от выхода к входу, то есть кратчайшим является путь = (0; i ₁; i ₂;...; i_{n -1}; n), такой, что и т.д.

Вопросы для самопроверки

1. Дайте определение графу.

2. Дайте определение ориентированному графу.

3. Дайте определение. неориентированному графу.

4. Дайте определение подграфу.

5. Дайте определение смежным вершинам.

6. Что такое инцидентность?

7. Что такое путь в графе?

8. Что такое контур графа?

9. Что такое Цепью графе?