Понятие кратчайшего пути

Задачи поиска путей минимальной общей длины, часто называемых кратчайшими путями, являются одними из наиболее исследованных и востребованных задач дискретной оптимиза-ции. Это связано с широкой распространённостью разнообразных прикладных задач, которые сводятся к поиску кратчайших путей. При этом в исходных постановках в качестве длин дуг или рёбер могут выступать расстояния, времена, стоимости, штрафы, убытки – словом, любая величина, которую желательно минимизировать и которая обладает свойством аддитивности или другими «декомпозиционными» свойствами, позволяющими использовать аналогичные модифицированные алгоритмы (примеры таких модификаций рассмотрены в разделе 4). Из множества методов нахождения кратчайших путей в главу включены два метода: алгоритм Дейкстры и алгоритм Флойда-Уоршолла. Различие между ними состоит в том, что первый на каждой итерации находит кратчайший путь от заданной вершины в некоторую другую; поэтому кратчайший путь между двумя фиксированными вершинами зачастую находится гораздо быст-рее, чем кратчайшие пути для всех пар вершин. Второй, напротив, в рамках одной процедуры находит кратчайшие пути сразу для всех пар вершин, что требуется в некоторых приложениях, но при этом вплоть до последней итерации нет гарантии, что кратчайший путь найден для лю-бой заранее указанной парой вершин. Однако алгоритм Флойда-Уоршолла «попутно» решает важную задачу о нахождении цикла отрицательной длины, к которой сводится хорошо известная задача о назначении (подробнее о ней говорится в следующей главе).

Для упрощения обозначений в данной главе рассматриваются простые ориентированные и неориентированные графы. Напомним, что простым называется граф (орграф), любые две вер-шины которого соединены не более чем одним ребром (двумя противоположно направленными дугами). Все понятия и результаты главы легко переносятся с неориентированных графов на ориентированные и наоборот. Переносятся они и на случай графов общего вида (с «параллель-ными» дугами или рёбрами), которые иногда называются мультиграфами (в этой терминологии графами называются только простые графы).

С каждой дугой (ребром) (x, y) заданного графа G ассоциировано число l (x, y), называемое длиной дуги. Содержательно это число может быть расстоянием, стоимостью, пропускной спо-собностью и т.д; Удобно считать, что рассматриваемые графы являются полными, т.е. любые две различные вершины соединены двумя противоположно ориентированными дугами (одним ребром), но для реально отсутствующих дуг l (x, y) = ¥.

С каждым путём P в графе (орграфе) G связано неотрицательное число L (P) (далее назы-ваемое длинойпути P). В этом и следующих двух разделах предполагается, что вес пути равен сумме длин входящих в него дуг. Для любых двух вершин графа G минимальным или кратчайшим путём называется любой соединяющий их путь P с минимальной длиной L (P). Подробнее: путь P, соединяющий заданные вершины a и b, называется минимальным или крат-чайшим, если для любого другого пути P', соединяющего те же самые вершины a и b, верно, что L (P) ≤ L (P'). В случаях, когда веса дуг могут быть отрицательными, задача нахождения кратчайшего пути в такой общей постановке может не иметь решения. В этих случаях обычно рассматриваются не все пути, а только простые пути или цепи (см. раздел 6-3), т.е. пути, про-ходящие через любую вершину или дугу не более одного раза.

Основными задачами, рассматриваемыми и решаемыми в настоящей главе, являются сле-дующие:

1) для заданной вершины найти кратчайшие пути, соединяющие её со всеми осталь-ными вершинами графа G;

2) для всех пар вершинграфа G найти соединяющие их кратчайшие пути.

Конечно, решение первой задачи, применённое ко всем вершинам графа, даёт решение второй задачи, а решение второй задачи даёт решение первой для всех вершин. Различие сос-тоит в алгоритмах, непосредственно направленных на решение либо первой, либо второй зада-чи. Одним из наиболее эффективных методов решения первой задачи является алгоритм Дейкстры (АД), а второй задачи – алгоритм Флойда-Уоршолла (АФУ).

Материал главы организован следующим образом. В разделе 2 вводится в рассмотрение и излагается АД. В разделе 3 вводится в рассмотрение и излагается алгоритм АФУ. Здесь же в от-дельном подразделе устанавливается возможность нахождения циклов отрицательной длины с помощью АФУ. В разделе 4 рассматривается другая зависимость длины пути от входящих в не-го рёбер (дуг). Именно, считается, что длиной пути является длина того ребра (той дуги), кото-рая является максимальной среди длин всех рёбер (дуг), входящих в данный путь.

Как и в других главах, изложение сопровождается иллюстрирующими примерами и зада-ниями.

Дата добавления: 2015-10-16