Определение длин кратчайших путей между всеми вершинами графа одновременно

Пусть матрица указывает длину дуг графа с числом вершин N. Элементы главной диагонали матрицы всегда равны нулю. Если между парой вершин отсутствует ветвь, то соответствующий элемент принимается равным бесконечности. Очевидно, матрица расстояний c¹(1,1) неориентированного графа всегда симметрична относительно своей главной диагонали; для ориентированного графа она может быть несимметричной. Возведем матрицу c¹(1,1) в квадрат с²(1,1) = c¹(1,1) c¹(1,1), где элемент.

с²_ij =.

Интерпретируя умножение как последовательное, а сложение как параллельное соединение дуг, легко понять, что произведение соответствует двухтранзитному пути (т.е. пути, проходящему через две транзитные дуги графа) от вершины i к вершине j через узел k. При этом произведение (),() фактически соответствует однотранзитным путям (включающим только одну ветвь), так как длины путей c_ii и c_jj равны нулю. Для подсчета длины каждого из таких транзитных путей необходимо операцию умножения заменить операцией сложения, т. е. вместо будем иметь. Если же имеется несколько параллельных путей, то для определения длины кратчайшего пути между вершинами необходимо операцию сложения в формуле для определения c²_ij заменить операцией выбора из всех длин однои двухтранзитных путей наименьшей длины, т. е.

Таким образом, элемент c²_ij матрицы с²(1,1) равен длине кратчайшего пути от вершины i к вершине j среди всех однои двухтранзитных путей.

При возведении с¹(1,1) в r-ю степень при использовании указанных выше операций получим матрицу c^r(1,1) = c^r-1(1,1)c¹(1,1), элемент которой, будет равен длине кратчайшего пути от вершины i к вершине j среди всех однотранзитных путей и т. д. до r-транзитных путей.

При наличии в графе N вершин число транзитных дуг в пути без петель не может быть больше N-1. Для конкретной сети может оказаться, что при r < N — 1 выполняется условие.

c^r(1,1) = c^r-1(1,1)c¹(1,1).

Тогда вычисление матрицы более высокой степени прекращается, так как при этом всегда выполняются равенства с^r+1(1,1) = c^r(1,1); c^N-1(1,1) = c^r-1(1,1). Матрица c^N-1(1,1) называется матрицей кратчайших путей. Рассмотренный способ позволяет определять длину кратчайшего пути, но не указывает дуги, которые входят в этот путь, однако в ряде задач такой информации бывает достаточно для принятия оптимального решения.

Решение задачи о кратчайшем пути в графе на основе линейного программирования [1,4]

Модель линейного программирования для задачи о кратчайшем пути строится следующим образом. Пусть X_ij, d_ij представляют соответственно величину и стоимость потока по дуге (i, j). Тогда задача о кратчайшем пути в сети с N узлами формулируется как :

минимизировать Z=.

при ограничениях.

=1 (исходный пункт),.

= (для всех к # 1 или N).

=1 (пункт назначения) Целевая функция требует, чтобы общее «расстояние», пройденное единицей потока, было минимальным. Здесь принято, что =1,если дуга (i, j) принадлежит кратчайшему пути и =0, если дуга (i, j) не принадлежит кратчайшему пути.