2.7. Поиск кратчайшего пути

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

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

Пусть задана связная сеть G из п + 1 вершин и т ребер, представленная в виде ориентированного графа, в котором выделены две вершины — вход (нулевая вершина) и выход (вершина с номером п). Для каждой дуги заданы неотрицательные числа, называемые длинами дуг. Сеть представляется матрицей смежности А, в которой:

Для решения задачи (2.10)—(2.12) часто используют алгоритм Дейкстры [8], который признан одним из лучших. Рассмотрим принципы его построения.

Для определения кратчайшего пути помечают все вершины сети, указав в качестве начальной Vq и конечной W вершин пути первую и последнюю вершины сети.

Шаг 1. Определяются непосредственные расстояния (длиной в одно ребро) от заданной вершины Vq до всех остальных вершин.

Шаг 2. Выбирается наименьшее из них в качестве «постоянного» наименьшего расстояния (ребро между Vq и некоторой новой вершиной Ѵд).

Шаг 3. Это наименьшее расстояние добавляется к длинам ребер от новой вершины Ѵа до всех остальных связанных с нею вершин.

Шаг 4. Эта сумма сравнивается с предыдущим расстоянием от Vq до остальных вершин, и прежнее расстояние заменяется, если новое меньше.

Шаг 5. Новая вершина удаляется из списка вершин, до которых ещё не определены кратчайшие расстояния, и список укорачивается на один элемент.

Затем весь этот процесс повторяется, присоединяется новое кратчайшее расстояние к списку и т.д., пока конечная вершина не окажется соединенной с Vq путем из выделенных ребер.

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