Пример Алгоритм Флойда

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

Пронумеруем все вершины графа, и составим матрицу длин кратчайших дуг D⁰, в случае, если дуги между вершиной i и j не существует, элементу d_i,j матрицы присваивается значение ∞. Исходный граф с пронумероваными вершинами представлен на рисунке ниже.

Матрица D⁰:

На основании матрицы 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¹, включив в нее рассчитанные элементы.

На основании матрицы 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², включив в нее рассчитанные элементы.

На основании матрицы 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³, включив в нее рассчитанные элементы.

На основании матрицы 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⁴, включив в нее рассчитанные элементы.

На основании матрицы 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⁵, включив в нее рассчитанные элементы.

На основании матрицы 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⁶, включив в нее рассчитанные элементы.

В результате, нами получена матрица длин кратчайших путей между каждой парой вершин графа. Ниже представлена таблица путей. Каждый элемент Cij таблицы, это путь из вершины i в вершину j: