Алгоритм Флойда - Уоршелла

Лабораторная работа 5

Наиболее часто используемое название, метод получил в честь двух американских исследователей Роберта Флойда и Стивена Уоршелла, одновременно открывших его в 1962 году. Реже встречаются другие варианты наименований: алгоритм Рой – Уоршелла или алгоритм Рой – Флойда. Рой – фамилия профессора, который разработал аналогичный алгоритм на 3 года раньше коллег (в 1959 г.), но это его открытие осталось безвестным

Алгоритм Флойда – Уоршелла – динамический алгоритм вычислений значений кратчайших путей для каждой из вершин графа. Метод работает на взвешенных графах, с положительными и отрицательными весами ребер, но без отрицательных циклов и является, таким образом, более общим, чем Алгоритм Дейкстры, который не работает с отрицательными весами и, в классической своей версии подразумевает определение оптимальных расстояний только от одной вершины до всех остальных

 

Для реализации алгоритма Флойда необходимо сформировать матрицу смежности исходного графа G(V,E), но каждому элементу матрицы присваивается вес ребра из вершины i в вершину j.

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

Пусть дана матрица весов дуг ориентированного графа G(V,E), необходимо определить кратчайшие расстояния между всеми парами вершин (v_i,v_j)

Шаг 1(присвоение начальных значений)

Установить номер итерации k =0. Построить матрицу смежности

Шаг 2(итерационный процесс)

Присвоить k = k +1.Для всех i, удовлетворяющих условию, и для всех, таких, что, , вычислить новые значения

Все другие элементы матрицы Dсохранить без изменений, т.е.

Шаг 3 (проверка условия окончания)

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

б) Если  и k=n, где n – количество вершин в графе, то решение получено. Конец алгоритма.

в) Если  и k<n, то переход к шагу 2.

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

 

Пример

Для графа, представленного на рисунке, найтикратчайшие пути для каждой из вершин

D⁰=      V⁰=

 

На основании матрицы D⁰, необходимо вычислить последовательно все элементы матрицы D¹. Для этого используется рекуррентное соотношение

d_i,j¹=min{ d_i,1+ d_1,j; d_i,j}.

d_1,1¹=min{d_1,1+d_1,1;d_1,1}=min{0+0; 0}=0

d_1,2¹=min{d_1,1+d_1,2;d_1,2}=min{0+10; 10}=10

d_1,3¹=min{d_1,1+d_1,3;d_1,3}=min{0+18; 18}=18

d_1,4¹=min{d_1,1+d_1,4;d_1,4}=min{0+8; 8}=8

d_1,5¹=min{d_1,1+d_1,5;d_1,5}=min{0+∞; ∞}=∞

d_1,6¹=min{d_1,1+d_1,6;d_1,6}=min{0+∞; ∞}=∞

d_2,1¹=min{d_2,1+d_1,1;d_2,1}=min{10+0; 10}=10

d_2,2¹=min{d_2,1+d_1,2;d_2,2}=min{10+10; 0}=0

d_2,3¹=min{d_2,1+d_1,3;d_2,3}=min{10+18; 16}=16

d_2,4¹=min{d_2,1+d_1,4;d_2,4}=min{10+8; 9}=9

d_2,5¹=min{d_2,1+d_1,5;d_2,5}=min{10+∞; 21}=21

d_2,6¹=min{d_2,1+d_1,6;d_2,6}=min{10+∞; ∞}=∞

d_3,1¹=min{d_3,1+d_1,1;d_3,1}=min{∞+0; ∞}=∞

d_3,2¹=min{d_3,1+d_1,2;d_3,2}=min{∞+10; 16}=16

d_3,3¹=min{d_3,1+d_1,3;d_3,3}=min{∞+18; 0}=0

d_3,4¹=min{d_3,1+d_1,4;d_3,4}=min{∞+8; ∞}=∞

d_3,5¹=min{d_3,1+d_1,5;d_3,5}=min{∞+∞; ∞}=∞

d_3,6¹=min{d_3,1+d_1,6;d_3,6}=min{∞+∞; 15}=15

d_4,1¹=min{d_4,1+d_1,1;d_4,1}=min{7+0; 7}=7

d_4,2¹=min{d_4,1+d_1,2;d_4,2}=min{7+10; 9}=9

d_4,3¹=min{d_4,1+d_1,3;d_4,3}=min{7+18; ∞}=25

d_4,4¹=min{d_4,1+d_1,4;d_4,4}=min{7+8; 0}=0

d_4,5¹=min{d_4,1+d_1,5;d_4,5}=min{7+∞; ∞}=∞

d_4,6¹=min{d_4,1+d_1,6;d_4,6}=min{7+∞; 12}=12

d_5,1¹=min{d_5,1+d_1,1;d_5,1}=min{∞+0; ∞}=∞

d_5,2¹=min{d_5,1+d_1,2;d_5,2}=min{∞+10; ∞}=∞

d_5,3¹=min{d_5,1+d_1,3;d_5,3}=min{∞+18; ∞}=∞

d_5,4¹=min{d_5,1+d_1,4;d_5,4}=min{∞+8; ∞}=∞

d_5,5¹=min{d_5,1+d_1,5;d_5,5}=min{∞+∞; 0}=0

d_5,6¹=min{d_5,1+d_1,6;d_5,6}=min{∞+∞; 23}=23

d_6,1¹=min{d_6,1+d_1,1;d_6,1}=min{∞+0; ∞}=∞

d_6,2¹=min{d_6,1+d_1,2;d_6,2}=min{∞+10; ∞}=∞

d_6,3¹=min{d_6,1+d_1,3;d_6,3}=min{∞+18; 15}=15

d_6,4¹=min{d_6,1+d_1,4;d_6,4}=min{∞+8; ∞}=∞

d_6,5¹=min{d_6,1+d_1,5;d_6,5}=min{∞+∞; 23}=23

d_6,6¹=min{d_6,1+d_1,6;d_6,6}=min{∞+∞; 0}=0

 

D¹=      V¹=

 

На основании матрицы D¹, необходимо вычислить последовательно все элементы матрицы D². Для этого используется рекуррентное соотношение

d_i,j²=min{ d_i,2¹+ d_2,j¹; d_i,j¹}.

d_1,1²=min{d_1,2¹+d_2,1¹d_1,1¹}=min{10+10; 0}=0

d_1,2²=min{d_1,2¹+d_2,2¹d_1,2¹}=min{10+0; 10}=10

d_1,3²=min{d_1,2¹+d_2,3¹d_1,3¹}=min{10+16; 18}=18

d_1,4²=min{d_1,2¹+d_2,4¹d_1,4¹}=min{10+9; 8}=8

d_1,5²=min{d_1,2¹+d_2,5¹d_1,5¹}=min{10+21; ∞}=31

d_1,6²=min{d_1,2¹+d_2,6¹d_1,6¹}=min{10+∞; ∞}=∞

d_2,1²=min{d_2,2¹+d_2,1¹d_2,1¹}=min{0+10; 10}=10

d_2,2²=min{d_2,2¹+d_2,2¹d_2,2¹}=min{0+0; 0}=0

d_2,3²=min{d_2,2¹+d_2,3¹d_2,3¹}=min{0+16; 16}=16

d_2,4²=min{d_2,2¹+d_2,4¹d_2,4¹}=min{0+9; 9}=9

d_2,5²=min{d_2,2¹+d_2,5¹d_2,5¹}=min{0+21; 21}=21 

d_2,6²=min{d_2,2¹+d_2,6¹d_2,6¹}=min{0+∞; ∞}=∞

d_3,1²=min{d_3,2¹+d_2,1¹d_3,1¹}=min{16+10; ∞}=26

d_3,2²=min{d_3,2¹+d_2,2¹d_3,2¹}=min{16+0; 16}=16

d_3,3²=min{d_3,2¹+d_2,3¹d_3,3¹}=min{16+16; 0}=0

d_3,4²=min{d_3,2¹+d_2,4¹d_3,4¹}=min{16+9; ∞}=25

d_3,5²=min{d_3,2¹+d_2,5¹d_3,5¹}=min{16+21; ∞}=37

d_3,6²=min{d_3,2¹+d_2,6¹d_3,6¹}=min{16+∞; 15}=15

d_4,1²=min{d_4,2¹+d_2,1¹d_4,1¹}=min{9+10; 7}=7

d_4,2²=min{d_4,2¹+d_2,2¹d_4,2¹}=min{9+0; 9}=9

d_4,3²=min{d_4,2¹+d_2,3¹d_4,3¹}=min{9+16; 25}=25

d_4,4²=min{d_4,2¹+d_2,4¹d_4,4¹}=min{9+9; 0}=0

d_4,5²=min{d_4,2¹+d_2,5¹d_4,5¹}=min{9+21; ∞}=30

d_4,6²=min{d_4,2¹+d_2,6¹d_4,6¹}=min{9+∞; 12}=12

d_5,1²=min{d_5,2¹+d_2,1¹d_5,1¹}=min{∞+10; ∞}=∞

d_5,2²=min{d_5,2¹+d_2,2¹d_5,2¹}=min{∞+0; ∞}=∞

d_5,3²=min{d_5,2¹+d_2,3¹d_5,3¹}=min{∞+16; ∞}=∞

d_5,4²=min{d_5,2¹+d_2,4¹d_5,4¹}=min{∞+9; ∞}=∞

d_5,5²=min{d_5,2¹+d_2,5¹d_5,5¹}=min{∞+21; 0}=0

d_5,6²=min{d_5,2¹+d_2,6¹d_5,6¹}=min{∞+∞; 23}=23

d_6,1²=min{d_6,2¹+d_2,1¹d_6,1¹}=min{∞+10; ∞}=∞

d_6,2²=min{d_6,2¹+d_2,2¹d_6,2¹}=min{∞+0; ∞}=∞

d_6,3²=min{d_6,2¹+d_2,3¹d_6,3¹}=min{∞+16; 15}=15

d_6,4²=min{d_6,2¹+d_2,4¹d_6,4¹}=min{∞+9; ∞}=∞

d_6,5²=min{d_6,2¹+d_2,5¹d_6,5¹}=min{∞+21; 23}=23

d_6,6²=min{d_6,2¹+d_2,6¹d_6,6¹}=min{∞+∞; 0}=0

 

D²=      V²=

На основании матрицы D², необходимо вычислить последовательно все элементы матрицы D³. Для этого используется рекуррентное соотношение

d_i,j³=min{ d_i,3²+ d_3,j²; d_i,j²}

d_1,1³=min{d_1,3²+d_3,1²d_1,1²}=min{18+26; 0}=0

d_1,2³=min{d_1,3²+d_3,2²d_1,2²}=min{18+16; 10}=10

d_1,3³=min{d_1,3²+d_3,3²d_1,3²}=min{18+0; 18}=18

d_1,4³=min{d_1,3²+d_3,4²d_1,4²}=min{18+25; 8}=8

d_1,5³=min{d_1,3²+d_3,5²d_1,5²}=min{18+37; 31}=31

d_1,6³=min{d_1,3²+d_3,6²d_1,6²}=min{18+15; ∞}=33

d_2,1³=min{d_2,3²+d_3,1²d_2,1²}=min{16+26; 10}=10

d_2,2³=min{d_2,3²+d_3,2²d_2,2²}=min{16+16; 0}=0

d_2,3³=min{d_2,3²+d_3,3²d_2,3²}=min{16+0; 16}=16

d_2,4³=min{d_2,3²+d_3,4²d_2,4²}=min{16+25; 9}=9

d_2,5³=min{d_2,3²+d_3,5²d_2,5²}=min{16+37; 21}=21

d_2,6³=min{d_2,3²+d_3,6²d_2,6²}=min{16+15; ∞}=31

d_3,1³=min{d_3,3²+d_3,1²d_3,1²}=min{0+26; 26}=26

d_3,2³=min{d_3,3²+d_3,2²d_3,2²}=min{0+16; 16}=16

d_3,3³=min{d_3,3²+d_3,3²d_3,3²}=min{0+0; 0}=0

d_3,4³=min{d_3,3²+d_3,4²d_3,4²}=min{0+25; 25}=25

d_3,5³=min{d_3,3²+d_3,5²d_3,5²}=min{0+37; 37}=37

d_3,6³=min{d_3,3²+d_3,6²d_3,6²}=min{0+15; 15}=15

d_4,1³=min{d_4,3²+d_3,1²d_4,1²}=min{25+26; 7}=7

d_4,2³=min{d_4,3²+d_3,2²d_4,2²}=min{25+16; 9}=9

d_4,3³=min{d_4,3²+d_3,3²d_4,3²}=min{25+0; 25}=25

d_4,4³=min{d_4,3²+d_3,4²d_4,4²}=min{25+25; 0}=0

d_4,5³=min{d_4,3²+d_3,5²d_4,5²}=min{25+37; 30}=30

d_4,6³=min{d_4,3²+d_3,6²d_4,6²}=min{25+15; 12}=12

d_5,1³=min{d_5,3²+d_3,1²d_5,1²}=min{∞+26; ∞}=∞

d_5,2³=min{d_5,3²+d_3,2²d_5,2²}=min{∞+16; ∞}=∞

d_5,3³=min{d_5,3²+d_3,3²d_5,3²}=min{∞+0; ∞}=∞

d_5,4³=min{d_5,3²+d_3,4²d_5,4²}=min{∞+25; ∞}=∞

d_5,5³=min{d_5,3²+d_3,5²d_5,5²}=min{∞+37; 0}=0

d_5,6³=min{d_5,3²+d_3,6²d_5,6²}=min{∞+15; 23}=23

d_6,1³=min{d_6,3²+d_3,1²d_6,1²}=min{15+26; ∞}=41

d_6,2³=min{d_6,3²+d_3,2²d_6,2²}=min{15+16; ∞}=31

d_6,3³=min{d_6,3²+d_3,3²d_6,3²}=min{15+0; 15}=15

d_6,4³=min{d_6,3²+d_3,4²d_6,4²}=min{15+25; ∞}=40

d_6,5³=min{d_6,3²+d_3,5²d_6,5²}=min{15+37; 23}=23

d_6,6³=min{d_6,3²+d_3,6²d_6,6²}=min{15+15; 0}=0

 

D³=      V³=

 

На основании матрицы D³, необходимо вычислить последовательно все элементы матрицы D⁴. Для этого используется рекуррентное соотношение

d_i,j⁴=min{ d_i,4³+ d_4,j³; d_i,j³}

d_1,1⁴=min{d_1,4³+d_4,1³d_1,1³}=min{8+7; 0}=0

d_1,2⁴=min{d_1,4³+d_4,2³d_1,2³}=min{8+9; 10}=10

d_1,3⁴=min{d_1,4³+d_4,3³d_1,3³}=min{8+25; 18}=18

d_1,4⁴=min{d_1,4³+d_4,4³d_1,4³}=min{8+0; 8}=8

d_1,5⁴=min{d_1,4³+d_4,5³d_1,5³}=min{8+30; 31}=31

d_1,6⁴=min{d_1,4³+d_4,6³d_1,6³}=min{8+12; 33}=20

d_2,1⁴=min{d_2,4³+d_4,1³d_2,1³}=min{9+7; 10}=10

d_2,2⁴=min{d_2,4³+d_4,2³d_2,2³}=min{9+9; 0}=0

d_2,3⁴=min{d_2,4³+d_4,3³d_2,3³}=min{9+25; 16}=16

d_2,4⁴=min{d_2,4³+d_4,4³d_2,4³}=min{9+0; 9}=9

d_2,5⁴=min{d_2,4³+d_4,5³d_2,5³}=min{9+30; 21}=21

d_2,6⁴=min{d_2,4³+d_4,6³d_2,6³}=min{9+12; 31}=21

d_3,1⁴=min{d_3,4³+d_4,1³d_3,1³}=min{25+7; 26}=26

d_3,2⁴=min{d_3,4³+d_4,2³d_3,2³}=min{25+9; 16}=16

d_3,3⁴=min{d_3,4³+d_4,3³d_3,3³}=min{25+25; 0}=0

d_3,4⁴=min{d_3,4³+d_4,4³d_3,4³}=min{25+0; 25}=25

d_3,5⁴=min{d_3,4³+d_4,5³d_3,5³}=min{25+30; 37}=37

d_3,6⁴=min{d_3,4³+d_4,6³d_3,6³}=min{25+12; 15}=15

d_4,1⁴=min{d_4,4³+d_4,1³d_4,1³}=min{0+7; 7}=7

d_4,2⁴=min{d_4,4³+d_4,2³d_4,2³}=min{0+9; 9}=9

d_4,3⁴=min{d_4,4³+d_4,3³d_4,3³}=min{0+25; 25}=25

d_4,4⁴=min{d_4,4³+d_4,4³d_4,4³}=min{0+0; 0}=0

d_4,5⁴=min{d_4,4³+d_4,5³d_4,5³}=min{0+30; 30}=30

d_4,6⁴=min{d_4,4³+d_4,6³d_4,6³}=min{0+12; 12}=12

d_5,1⁴=min{d_5,4³+d_4,1³d_5,1³}=min{∞+7; ∞}=∞

d_5,2⁴=min{d_5,4³+d_4,2³d_5,2³}=min{∞+9; ∞}=∞

d_5,3⁴=min{d_5,4³+d_4,3³d_5,3³}=min{∞+25; ∞}=∞

d_5,4⁴=min{d_5,4³+d_4,4³d_5,4³}=min{∞+0; ∞}=∞

d_5,5⁴=min{d_5,4³+d_4,5³d_5,5³}=min{∞+30; 0}=0

d_5,6⁴=min{d_5,4³+d_4,6³d_5,6³}=min{∞+12; 23}=23

d_6,1⁴=min{d_6,4³+d_4,1³d_6,1³}=min{40+7; 41}=41

d_6,2⁴=min{d_6,4³+d_4,2³d_6,2³}=min{40+9; 31}=31

d_6,3⁴=min{d_6,4³+d_4,3³d_6,3³}=min{40+25; 15}=15

d_6,4⁴=min{d_6,4³+d_4,4³d_6,4³}=min{40+0; 40}=40

d_6,5⁴=min{d_6,4³+d_4,5³d_6,5³}=min{40+30; 23}=23

d_6,6⁴=min{d_6,4³+d_4,6³d_6,6³}=min{40+12; 0}=0

 

D⁴=      V⁴=

На основании матрицы D⁴, необходимо вычислить последовательно все элементы матрицы D⁵. Для этого используется рекуррентное соотношение

d_i,j⁵=min{ d_i,5⁴+ d_5,j⁴; d_i,j⁴}

d_1,1⁵=min{d_1,5⁴+d_5,1⁴d_1,1⁴}=min{31+∞; 0}=0

d_1,2⁵=min{d_1,5⁴+d_5,2⁴d_1,2⁴}=min{31+∞; 10}=10

d_1,3⁵=min{d_1,5⁴+d_5,3⁴d_1,3⁴}=min{31+∞; 18}=18

d_1,4⁵=min{d_1,5⁴+d_5,4⁴d_1,4⁴}=min{31+∞; 8}=8

d_1,5⁵=min{d_1,5⁴+d_5,5⁴d_1,5⁴}=min{31+0; 31}=31

d_1,6⁵=min{d_1,5⁴+d_5,6⁴d_1,6⁴}=min{31+23; 20}=20

d_2,1⁵=min{d_2,5⁴+d_5,1⁴d_2,1⁴}=min{21+∞; 10}=10

d_2,2⁵=min{d_2,5⁴+d_5,2⁴d_2,2⁴}=min{21+∞; 0}=0

d_2,3⁵=min{d_2,5⁴+d_5,3⁴d_2,3⁴}=min{21+∞; 16}=16

d_2,4⁵=min{d_2,5⁴+d_5,4⁴d_2,4⁴}=min{21+∞; 9}=9

d_2,5⁵=min{d_2,5⁴+d_5,5⁴d_2,5⁴}=min{21+0; 21}=21

d_2,6⁵=min{d_2,5⁴+d_5,6⁴d_2,6⁴}=min{21+23; 21}=21

d_3,1⁵=min{d_3,5⁴+d_5,1⁴d_3,1⁴}=min{37+∞; 26}=26

d_3,2⁵=min{d_3,5⁴+d_5,2⁴d_3,2⁴}=min{37+∞; 16}=16

d_3,3⁵=min{d_3,5⁴+d_5,3⁴d_3,3⁴}=min{37+∞; 0}=0

d_3,4⁵=min{d_3,5⁴+d_5,4⁴d_3,4⁴}=min{37+∞; 25}=25

d_3,5⁵=min{d_3,5⁴+d_5,5⁴d_3,5⁴}=min{37+0; 37}=37

d_3,6⁵=min{d_3,5⁴+d_5,6⁴d_3,6⁴}=min{37+23; 15}=15

d_4,1⁵=min{d_4,5⁴+d_5,1⁴d_4,1⁴}=min{30+∞; 7}=7

d_4,2⁵=min{d_4,5⁴+d_5,2⁴d_4,2⁴}=min{30+∞; 9}=9

d_4,3⁵=min{d_4,5⁴+d_5,3⁴d_4,3⁴}=min{30+∞; 25}=25

d_4,4⁵=min{d_4,5⁴+d_5,4⁴d_4,4⁴}=min{30+∞; 0}=0

d_4,5⁵=min{d_4,5⁴+d_5,5⁴d_4,5⁴}=min{30+0; 30}=30

d_4,6⁵=min{d_4,5⁴+d_5,6⁴d_4,6⁴}=min{30+23; 12}=12

d_5,1⁵=min{d_5,5⁴+d_5,1⁴d_5,1⁴}=min{0+∞; ∞}=∞

d_5,2⁵=min{d_5,5⁴+d_5,2⁴d_5,2⁴}=min{0+∞; ∞}=∞

d_5,3⁵=min{d_5,5⁴+d_5,3⁴d_5,3⁴}=min{0+∞; ∞}=∞

d_5,4⁵=min{d_5,5⁴+d_5,4⁴d_5,4⁴}=min{0+∞; ∞}=∞

d_5,5⁵=min{d_5,5⁴+d_5,5⁴d_5,5⁴}=min{0+0; 0}=0

d_5,6⁵=min{d_5,5⁴+d_5,6⁴d_5,6⁴}=min{0+23; 23}=23

d_6,1⁵=min{d_6,5⁴+d_5,1⁴d_6,1⁴}=min{23+∞; 41}=41

d_6,2⁵=min{d_6,5⁴+d_5,2⁴d_6,2⁴}=min{23+∞; 31}=31

d_6,3⁵=min{d_6,5⁴+d_5,3⁴d_6,3⁴}=min{23+∞; 15}=15

d_6,4⁵=min{d_6,5⁴+d_5,4⁴d_6,4⁴}=min{23+∞; 40}=40

d_6,5⁵=min{d_6,5⁴+d_5,5⁴d_6,5⁴}=min{23+0; 23}=23

d_6,6⁵=min{d_6,5⁴+d_5,6⁴d_6,6⁴}=min{23+23; 0}=0

 

D⁵=      V⁵=

На основании матрицы D⁵, необходимо вычислить последовательно все элементы матрицы D⁶. Для этого используется рекуррентное соотношение

d_i,j⁶=min{ d_i,6⁵+ d_6,j⁵; d_i,j⁵}.

d_1,1⁶=min{d_1,6⁵+d_6,1⁵d_1,1⁵}=min{20+41; 0}=0

d_1,2⁶=min{d_1,6⁵+d_6,2⁵d_1,2⁵}=min{20+31; 10}=10

d_1,3⁶=min{d_1,6⁵+d_6,3⁵d_1,3⁵}=min{20+15; 18}=18

d_1,4⁶=min{d_1,6⁵+d_6,4⁵d_1,4⁵}=min{20+40; 8}=8

d_1,5⁶=min{d_1,6⁵+d_6,5⁵d_1,5⁵}=min{20+23; 31}=31

d_1,6⁶=min{d_1,6⁵+d_6,6⁵d_1,6⁵}=min{20+0; 20}=20

d_2,1⁶=min{d_2,6⁵+d_6,1⁵d_2,1⁵}=min{21+41; 10}=10

d_2,2⁶=min{d_2,6⁵+d_6,2⁵d_2,2⁵}=min{21+31; 0}=0

d_2,3⁶=min{d_2,6⁵+d_6,3⁵d_2,3⁵}=min{21+15; 16}=16

d_2,4⁶=min{d_2,6⁵+d_6,4⁵d_2,4⁵}=min{21+40; 9}=9

d_2,5⁶=min{d_2,6⁵+d_6,5⁵d_2,5⁵}=min{21+23; 21}=21

d_2,6⁶=min{d_2,6⁵+d_6,6⁵d_2,6⁵}=min{21+0; 21}=21

d_3,1⁶=min{d_3,6⁵+d_6,1⁵d_3,1⁵}=min{15+41; 26}=26

d_3,2⁶=min{d_3,6⁵+d_6,2⁵d_3,2⁵}=min{15+31; 16}=16

d_3,3⁶=min{d_3,6⁵+d_6,3⁵d_3,3⁵}=min{15+15; 0}=0

d_3,4⁶=min{d_3,6⁵+d_6,4⁵d_3,4⁵}=min{15+40; 25}=25

d_3,5⁶=min{d_3,6⁵+d_6,5⁵d_3,5⁵}=min{15+23; 37}=37

d_3,6⁶=min{d_3,6⁵+d_6,6⁵d_3,6⁵}=min{15+0; 15}=15

d_4,1⁶=min{d_4,6⁵+d_6,1⁵d_4,1⁵}=min{12+41; 7}=7

d_4,2⁶=min{d_4,6⁵+d_6,2⁵d_4,2⁵}=min{12+31; 9}=9

d_4,3⁶=min{d_4,6⁵+d_6,3⁵d_4,3⁵}=min{12+15; 25}=25

d_4,4⁶=min{d_4,6⁵+d_6,4⁵d_4,4⁵}=min{12+40; 0}=0

d_4,5⁶=min{d_4,6⁵+d_6,5⁵d_4,5⁵}=min{12+23; 30}=30

d_4,6⁶=min{d_4,6⁵+d_6,6⁵d_4,6⁵}=min{12+0; 12}=12

d_5,1⁶=min{d_5,6⁵+d_6,1⁵d_5,1⁵}=min{23+41; ∞}=64

d_5,2⁶=min{d_5,6⁵+d_6,2⁵d_5,2⁵}=min{23+31; ∞}=54

d_5,3⁶=min{d_5,6⁵+d_6,3⁵d_5,3⁵}=min{23+15; ∞}=38

d_5,4⁶=min{d_5,6⁵+d_6,4⁵d_5,4⁵}=min{23+40; ∞}=63

d_5,5⁶=min{d_5,6⁵+d_6,5⁵d_5,5⁵}=min{23+23; 0}=0

d_5,6⁶=min{d_5,6⁵+d_6,6⁵d_5,6⁵}=min{23+0; 23}=23

d_6,1⁶=min{d_6,6⁵+d_6,1⁵d_6,1⁵}=min{0+41; 41}=41

d_6,2⁶=min{d_6,6⁵+d_6,2⁵d_6,2⁵}=min{0+31; 31}=31

d_6,3⁶=min{d_6,6⁵+d_6,3⁵d_6,3⁵}=min{0+15; 15}=15

d_6,4⁶=min{d_6,6⁵+d_6,4⁵d_6,4⁵}=min{0+40; 40}=40

d_6,5⁶=min{d_6,6⁵+d_6,5⁵d_6,5⁵}=min{0+23; 23}=23

d_6,6⁶=min{d_6,6⁵+d_6,6⁵d_6,6⁵}=min{0+0; 0}=0

 

D⁶=      V⁶=

В результате получены матрица D⁶ – значений всех кратчайших путей из любой вершины в любую и матрица V⁶ – индексов вершин, составляющих эти пути.

Восстановим для примера пути из вершины v₄:

v₄v_{1 ;} значение пути определяется по матрице смежности D⁶ и равно 8, индекс пути определяется по матрице V⁶ и равен 1, что означает наличие прямого пути из вершины v₄ в вершину v₁

v₄v_{2 ;} значение пути равно 9, индекс пути 2, что означает наличие прямого пути из вершины v₄ в вершину v₂

v₄v₃: значение пути равно 25, индекс пути 1, 3, восстановленный путь v₄v₁v₃

v₄v₅: значение пути равно 30, индекс пути 2, 5, восстановленный путь v₄v₂v₅

v₄v₆: значение пути равно 12, индекс пути 6, что означает наличие прямого пути из вершины v₄ в вершину v₆

Задание

Найтикратчайшие пути для графов, представленных задании к Лабораторной работе 4 (Алгоритм Дейкстры). Граф для решения выбрать в соответствии со своим номером в списке группы.