Всеми вершинами графа одновременно

Пусть матрица указывает длину дуг графа с числом вершин 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) называется матрицей кратчайших путей. Рассмотренный способ позволяет определять длину кратчайшего пути, но не указывает дуги, которые входят в этот путь, однако в ряде задач такой информации бывает достаточно для принятия оптимального решения.