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

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

граф

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

граф с перенумированными вершинами

Матрица D:

D= 10 18 8
10 16 9 21
16 15
7 9 12
23
15 23

На основании матрицы D, вычислим последовательно все элементы матрицы D1. Для этого мы используем рекуррентное соотношение di,j1=min{ di,1+ d1,j; di,j}.
d1,11=min{d1,1+d1,1d1,1}=min{0+0; 0}=0
d1,21=min{d1,1+d1,2d1,2}=min{0+10; 10}=10
d1,31=min{d1,1+d1,3d1,3}=min{0+18; 18}=18
d1,41=min{d1,1+d1,4d1,4}=min{0+8; 8}=8
d1,51=min{d1,1+d1,5d1,5}=min{0+∞; ∞}=∞
d1,61=min{d1,1+d1,6d1,6}=min{0+∞; ∞}=∞
d2,11=min{d2,1+d1,1d2,1}=min{10+0; 10}=10
d2,21=min{d2,1+d1,2d2,2}=min{10+10; 0}=0
d2,31=min{d2,1+d1,3d2,3}=min{10+18; 16}=16
d2,41=min{d2,1+d1,4d2,4}=min{10+8; 9}=9
d2,51=min{d2,1+d1,5d2,5}=min{10+∞; 21}=21
d2,61=min{d2,1+d1,6d2,6}=min{10+∞; ∞}=∞
d3,11=min{d3,1+d1,1d3,1}=min{∞+0; ∞}=∞
d3,21=min{d3,1+d1,2d3,2}=min{∞+10; 16}=16
d3,31=min{d3,1+d1,3d3,3}=min{∞+18; 0}=0
d3,41=min{d3,1+d1,4d3,4}=min{∞+8; ∞}=∞
d3,51=min{d3,1+d1,5d3,5}=min{∞+∞; ∞}=∞
d3,61=min{d3,1+d1,6d3,6}=min{∞+∞; 15}=15
d4,11=min{d4,1+d1,1d4,1}=min{7+0; 7}=7
d4,21=min{d4,1+d1,2d4,2}=min{7+10; 9}=9
d4,31=min{d4,1+d1,3d4,3}=min{7+18; ∞}=25
d4,41=min{d4,1+d1,4d4,4}=min{7+8; 0}=0
d4,51=min{d4,1+d1,5d4,5}=min{7+∞; ∞}=∞
d4,61=min{d4,1+d1,6d4,6}=min{7+∞; 12}=12
d5,11=min{d5,1+d1,1d5,1}=min{∞+0; ∞}=∞
d5,21=min{d5,1+d1,2d5,2}=min{∞+10; ∞}=∞
d5,31=min{d5,1+d1,3d5,3}=min{∞+18; ∞}=∞
d5,41=min{d5,1+d1,4d5,4}=min{∞+8; ∞}=∞
d5,51=min{d5,1+d1,5d5,5}=min{∞+∞; 0}=0
d5,61=min{d5,1+d1,6d5,6}=min{∞+∞; 23}=23
d6,11=min{d6,1+d1,1d6,1}=min{∞+0; ∞}=∞
d6,21=min{d6,1+d1,2d6,2}=min{∞+10; ∞}=∞
d6,31=min{d6,1+d1,3d6,3}=min{∞+18; 15}=15
d6,41=min{d6,1+d1,4d6,4}=min{∞+8; ∞}=∞
d6,51=min{d6,1+d1,5d6,5}=min{∞+∞; 23}=23
d6,61=min{d6,1+d1,6d6,6}=min{∞+∞; 0}=0
Представим матрицу D1, включив в нее рассчитанные элементы.

D1= 10 18 8
10 16 9 21
16 15
7 9 25 12
23
15 23

На основании матрицы D1, вычислим последовательно все элементы матрицы D2. Для этого мы используем рекуррентное соотношение di,j2=min{ di,21+ d2,j1; di,j1}.
d1,12=min{d1,21+d2,11d1,11}=min{10+10; 0}=0
d1,22=min{d1,21+d2,21d1,21}=min{10+0; 10}=10
d1,32=min{d1,21+d2,31d1,31}=min{10+16; 18}=18
d1,42=min{d1,21+d2,41d1,41}=min{10+9; 8}=8
d1,52=min{d1,21+d2,51d1,51}=min{10+21; ∞}=31
d1,62=min{d1,21+d2,61d1,61}=min{10+∞; ∞}=∞
d2,12=min{d2,21+d2,11d2,11}=min{0+10; 10}=10
d2,22=min{d2,21+d2,21d2,21}=min{0+0; 0}=0
d2,32=min{d2,21+d2,31d2,31}=min{0+16; 16}=16
d2,42=min{d2,21+d2,41d2,41}=min{0+9; 9}=9
d2,52=min{d2,21+d2,51d2,51}=min{0+21; 21}=21
d2,62=min{d2,21+d2,61d2,61}=min{0+∞; ∞}=∞
d3,12=min{d3,21+d2,11d3,11}=min{16+10; ∞}=26
d3,22=min{d3,21+d2,21d3,21}=min{16+0; 16}=16
d3,32=min{d3,21+d2,31d3,31}=min{16+16; 0}=0
d3,42=min{d3,21+d2,41d3,41}=min{16+9; ∞}=25
d3,52=min{d3,21+d2,51d3,51}=min{16+21; ∞}=37
d3,62=min{d3,21+d2,61d3,61}=min{16+∞; 15}=15
d4,12=min{d4,21+d2,11d4,11}=min{9+10; 7}=7
d4,22=min{d4,21+d2,21d4,21}=min{9+0; 9}=9
d4,32=min{d4,21+d2,31d4,31}=min{9+16; 25}=25
d4,42=min{d4,21+d2,41d4,41}=min{9+9; 0}=0
d4,52=min{d4,21+d2,51d4,51}=min{9+21; ∞}=30
d4,62=min{d4,21+d2,61d4,61}=min{9+∞; 12}=12
d5,12=min{d5,21+d2,11d5,11}=min{∞+10; ∞}=∞
d5,22=min{d5,21+d2,21d5,21}=min{∞+0; ∞}=∞
d5,32=min{d5,21+d2,31d5,31}=min{∞+16; ∞}=∞
d5,42=min{d5,21+d2,41d5,41}=min{∞+9; ∞}=∞
d5,52=min{d5,21+d2,51d5,51}=min{∞+21; 0}=0
d5,62=min{d5,21+d2,61d5,61}=min{∞+∞; 23}=23
d6,12=min{d6,21+d2,11d6,11}=min{∞+10; ∞}=∞
d6,22=min{d6,21+d2,21d6,21}=min{∞+0; ∞}=∞
d6,32=min{d6,21+d2,31d6,31}=min{∞+16; 15}=15
d6,42=min{d6,21+d2,41d6,41}=min{∞+9; ∞}=∞
d6,52=min{d6,21+d2,51d6,51}=min{∞+21; 23}=23
d6,62=min{d6,21+d2,61d6,61}=min{∞+∞; 0}=0
Представим матрицу D2, включив в нее рассчитанные элементы.

Читайте также  Вычислительная сложность алгоритма
D2= 10 18 8 31
10 16 9 21
26 16 25 37 15
7 9 25 30 12
23
15 23

На основании матрицы D2, вычислим последовательно все элементы матрицы D3. Для этого мы используем рекуррентное соотношение di,j3=min{ di,32+ d3,j2; di,j2}.
d1,13=min{d1,32+d3,12d1,12}=min{18+26; 0}=0
d1,23=min{d1,32+d3,22d1,22}=min{18+16; 10}=10
d1,33=min{d1,32+d3,32d1,32}=min{18+0; 18}=18
d1,43=min{d1,32+d3,42d1,42}=min{18+25; 8}=8
d1,53=min{d1,32+d3,52d1,52}=min{18+37; 31}=31
d1,63=min{d1,32+d3,62d1,62}=min{18+15; ∞}=33
d2,13=min{d2,32+d3,12d2,12}=min{16+26; 10}=10
d2,23=min{d2,32+d3,22d2,22}=min{16+16; 0}=0
d2,33=min{d2,32+d3,32d2,32}=min{16+0; 16}=16
d2,43=min{d2,32+d3,42d2,42}=min{16+25; 9}=9
d2,53=min{d2,32+d3,52d2,52}=min{16+37; 21}=21
d2,63=min{d2,32+d3,62d2,62}=min{16+15; ∞}=31
d3,13=min{d3,32+d3,12d3,12}=min{0+26; 26}=26
d3,23=min{d3,32+d3,22d3,22}=min{0+16; 16}=16
d3,33=min{d3,32+d3,32d3,32}=min{0+0; 0}=0
d3,43=min{d3,32+d3,42d3,42}=min{0+25; 25}=25
d3,53=min{d3,32+d3,52d3,52}=min{0+37; 37}=37
d3,63=min{d3,32+d3,62d3,62}=min{0+15; 15}=15
d4,13=min{d4,32+d3,12d4,12}=min{25+26; 7}=7
d4,23=min{d4,32+d3,22d4,22}=min{25+16; 9}=9
d4,33=min{d4,32+d3,32d4,32}=min{25+0; 25}=25
d4,43=min{d4,32+d3,42d4,42}=min{25+25; 0}=0
d4,53=min{d4,32+d3,52d4,52}=min{25+37; 30}=30
d4,63=min{d4,32+d3,62d4,62}=min{25+15; 12}=12
d5,13=min{d5,32+d3,12d5,12}=min{∞+26; ∞}=∞
d5,23=min{d5,32+d3,22d5,22}=min{∞+16; ∞}=∞
d5,33=min{d5,32+d3,32d5,32}=min{∞+0; ∞}=∞
d5,43=min{d5,32+d3,42d5,42}=min{∞+25; ∞}=∞
d5,53=min{d5,32+d3,52d5,52}=min{∞+37; 0}=0
d5,63=min{d5,32+d3,62d5,62}=min{∞+15; 23}=23
d6,13=min{d6,32+d3,12d6,12}=min{15+26; ∞}=41
d6,23=min{d6,32+d3,22d6,22}=min{15+16; ∞}=31
d6,33=min{d6,32+d3,32d6,32}=min{15+0; 15}=15
d6,43=min{d6,32+d3,42d6,42}=min{15+25; ∞}=40
d6,53=min{d6,32+d3,52d6,52}=min{15+37; 23}=23
d6,63=min{d6,32+d3,62d6,62}=min{15+15; 0}=0
Представим матрицу D3, включив в нее рассчитанные элементы.

D3= 10 18 8 31 33
10 16 9 21 31
26 16 25 37 15
7 9 25 30 12
23
41 31 15 40 23

На основании матрицы D3, вычислим последовательно все элементы матрицы D4. Для этого мы используем рекуррентное соотношение di,j4=min{ di,43+ d4,j3; di,j3}.
d1,14=min{d1,43+d4,13d1,13}=min{8+7; 0}=0
d1,24=min{d1,43+d4,23d1,23}=min{8+9; 10}=10
d1,34=min{d1,43+d4,33d1,33}=min{8+25; 18}=18
d1,44=min{d1,43+d4,43d1,43}=min{8+0; 8}=8
d1,54=min{d1,43+d4,53d1,53}=min{8+30; 31}=31
d1,64=min{d1,43+d4,63d1,63}=min{8+12; 33}=20
d2,14=min{d2,43+d4,13d2,13}=min{9+7; 10}=10
d2,24=min{d2,43+d4,23d2,23}=min{9+9; 0}=0
d2,34=min{d2,43+d4,33d2,33}=min{9+25; 16}=16
d2,44=min{d2,43+d4,43d2,43}=min{9+0; 9}=9
d2,54=min{d2,43+d4,53d2,53}=min{9+30; 21}=21
d2,64=min{d2,43+d4,63d2,63}=min{9+12; 31}=21
d3,14=min{d3,43+d4,13d3,13}=min{25+7; 26}=26
d3,24=min{d3,43+d4,23d3,23}=min{25+9; 16}=16
d3,34=min{d3,43+d4,33d3,33}=min{25+25; 0}=0
d3,44=min{d3,43+d4,43d3,43}=min{25+0; 25}=25
d3,54=min{d3,43+d4,53d3,53}=min{25+30; 37}=37
d3,64=min{d3,43+d4,63d3,63}=min{25+12; 15}=15
d4,14=min{d4,43+d4,13d4,13}=min{0+7; 7}=7
d4,24=min{d4,43+d4,23d4,23}=min{0+9; 9}=9
d4,34=min{d4,43+d4,33d4,33}=min{0+25; 25}=25
d4,44=min{d4,43+d4,43d4,43}=min{0+0; 0}=0
d4,54=min{d4,43+d4,53d4,53}=min{0+30; 30}=30
d4,64=min{d4,43+d4,63d4,63}=min{0+12; 12}=12
d5,14=min{d5,43+d4,13d5,13}=min{∞+7; ∞}=∞
d5,24=min{d5,43+d4,23d5,23}=min{∞+9; ∞}=∞
d5,34=min{d5,43+d4,33d5,33}=min{∞+25; ∞}=∞
d5,44=min{d5,43+d4,43d5,43}=min{∞+0; ∞}=∞
d5,54=min{d5,43+d4,53d5,53}=min{∞+30; 0}=0
d5,64=min{d5,43+d4,63d5,63}=min{∞+12; 23}=23
d6,14=min{d6,43+d4,13d6,13}=min{40+7; 41}=41
d6,24=min{d6,43+d4,23d6,23}=min{40+9; 31}=31
d6,34=min{d6,43+d4,33d6,33}=min{40+25; 15}=15
d6,44=min{d6,43+d4,43d6,43}=min{40+0; 40}=40
d6,54=min{d6,43+d4,53d6,53}=min{40+30; 23}=23
d6,64=min{d6,43+d4,63d6,63}=min{40+12; 0}=0
Представим матрицу D4, включив в нее рассчитанные элементы.

Читайте также  Центр графа
D4= 10 18 8 31 20
10 16 9 21 21
26 16 25 37 15
7 9 25 30 12
23
41 31 15 40 23

На основании матрицы D4, вычислим последовательно все элементы матрицы D5. Для этого мы используем рекуррентное соотношение di,j5=min{ di,54+ d5,j4; di,j4}.
d1,15=min{d1,54+d5,14d1,14}=min{31+∞; 0}=0
d1,25=min{d1,54+d5,24d1,24}=min{31+∞; 10}=10
d1,35=min{d1,54+d5,34d1,34}=min{31+∞; 18}=18
d1,45=min{d1,54+d5,44d1,44}=min{31+∞; 8}=8
d1,55=min{d1,54+d5,54d1,54}=min{31+0; 31}=31
d1,65=min{d1,54+d5,64d1,64}=min{31+23; 20}=20
d2,15=min{d2,54+d5,14d2,14}=min{21+∞; 10}=10
d2,25=min{d2,54+d5,24d2,24}=min{21+∞; 0}=0
d2,35=min{d2,54+d5,34d2,34}=min{21+∞; 16}=16
d2,45=min{d2,54+d5,44d2,44}=min{21+∞; 9}=9
d2,55=min{d2,54+d5,54d2,54}=min{21+0; 21}=21
d2,65=min{d2,54+d5,64d2,64}=min{21+23; 21}=21
d3,15=min{d3,54+d5,14d3,14}=min{37+∞; 26}=26
d3,25=min{d3,54+d5,24d3,24}=min{37+∞; 16}=16
d3,35=min{d3,54+d5,34d3,34}=min{37+∞; 0}=0
d3,45=min{d3,54+d5,44d3,44}=min{37+∞; 25}=25
d3,55=min{d3,54+d5,54d3,54}=min{37+0; 37}=37
d3,65=min{d3,54+d5,64d3,64}=min{37+23; 15}=15
d4,15=min{d4,54+d5,14d4,14}=min{30+∞; 7}=7
d4,25=min{d4,54+d5,24d4,24}=min{30+∞; 9}=9
d4,35=min{d4,54+d5,34d4,34}=min{30+∞; 25}=25
d4,45=min{d4,54+d5,44d4,44}=min{30+∞; 0}=0
d4,55=min{d4,54+d5,54d4,54}=min{30+0; 30}=30
d4,65=min{d4,54+d5,64d4,64}=min{30+23; 12}=12
d5,15=min{d5,54+d5,14d5,14}=min{0+∞; ∞}=∞
d5,25=min{d5,54+d5,24d5,24}=min{0+∞; ∞}=∞
d5,35=min{d5,54+d5,34d5,34}=min{0+∞; ∞}=∞
d5,45=min{d5,54+d5,44d5,44}=min{0+∞; ∞}=∞
d5,55=min{d5,54+d5,54d5,54}=min{0+0; 0}=0
d5,65=min{d5,54+d5,64d5,64}=min{0+23; 23}=23
d6,15=min{d6,54+d5,14d6,14}=min{23+∞; 41}=41
d6,25=min{d6,54+d5,24d6,24}=min{23+∞; 31}=31
d6,35=min{d6,54+d5,34d6,34}=min{23+∞; 15}=15
d6,45=min{d6,54+d5,44d6,44}=min{23+∞; 40}=40
d6,55=min{d6,54+d5,54d6,54}=min{23+0; 23}=23
d6,65=min{d6,54+d5,64d6,64}=min{23+23; 0}=0
Представим матрицу D5, включив в нее рассчитанные элементы.

Читайте также  Алгоритм Флойда (поиск всех кратчайших путей в графе)
D5= 10 18 8 31 20
10 16 9 21 21
26 16 25 37 15
7 9 25 30 12
23
41 31 15 40 23

На основании матрицы D5, вычислим последовательно все элементы матрицы D6. Для этого мы используем рекуррентное соотношение di,j6=min{ di,65+ d6,j5; di,j5}.
d1,16=min{d1,65+d6,15d1,15}=min{20+41; 0}=0
d1,26=min{d1,65+d6,25d1,25}=min{20+31; 10}=10
d1,36=min{d1,65+d6,35d1,35}=min{20+15; 18}=18
d1,46=min{d1,65+d6,45d1,45}=min{20+40; 8}=8
d1,56=min{d1,65+d6,55d1,55}=min{20+23; 31}=31
d1,66=min{d1,65+d6,65d1,65}=min{20+0; 20}=20
d2,16=min{d2,65+d6,15d2,15}=min{21+41; 10}=10
d2,26=min{d2,65+d6,25d2,25}=min{21+31; 0}=0
d2,36=min{d2,65+d6,35d2,35}=min{21+15; 16}=16
d2,46=min{d2,65+d6,45d2,45}=min{21+40; 9}=9
d2,56=min{d2,65+d6,55d2,55}=min{21+23; 21}=21
d2,66=min{d2,65+d6,65d2,65}=min{21+0; 21}=21
d3,16=min{d3,65+d6,15d3,15}=min{15+41; 26}=26
d3,26=min{d3,65+d6,25d3,25}=min{15+31; 16}=16
d3,36=min{d3,65+d6,35d3,35}=min{15+15; 0}=0
d3,46=min{d3,65+d6,45d3,45}=min{15+40; 25}=25
d3,56=min{d3,65+d6,55d3,55}=min{15+23; 37}=37
d3,66=min{d3,65+d6,65d3,65}=min{15+0; 15}=15
d4,16=min{d4,65+d6,15d4,15}=min{12+41; 7}=7
d4,26=min{d4,65+d6,25d4,25}=min{12+31; 9}=9
d4,36=min{d4,65+d6,35d4,35}=min{12+15; 25}=25
d4,46=min{d4,65+d6,45d4,45}=min{12+40; 0}=0
d4,56=min{d4,65+d6,55d4,55}=min{12+23; 30}=30
d4,66=min{d4,65+d6,65d4,65}=min{12+0; 12}=12
d5,16=min{d5,65+d6,15d5,15}=min{23+41; ∞}=64
d5,26=min{d5,65+d6,25d5,25}=min{23+31; ∞}=54
d5,36=min{d5,65+d6,35d5,35}=min{23+15; ∞}=38
d5,46=min{d5,65+d6,45d5,45}=min{23+40; ∞}=63
d5,56=min{d5,65+d6,55d5,55}=min{23+23; 0}=0
d5,66=min{d5,65+d6,65d5,65}=min{23+0; 23}=23
d6,16=min{d6,65+d6,15d6,15}=min{0+41; 41}=41
d6,26=min{d6,65+d6,25d6,25}=min{0+31; 31}=31
d6,36=min{d6,65+d6,35d6,35}=min{0+15; 15}=15
d6,46=min{d6,65+d6,45d6,45}=min{0+40; 40}=40
d6,56=min{d6,65+d6,55d6,55}=min{0+23; 23}=23
d6,66=min{d6,65+d6,65d6,65}=min{0+0; 0}=0
Представим матрицу D6, включив в нее рассчитанные элементы.

D6= 10 18 8 31 20
10 16 9 21 21
26 16 25 37 15
7 9 25 30 12
64 54 38 63 23
41 31 15 40 23

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

Таблица путей
1 2 3 4 5 6
1 d1-2=1-2 d1-3=1-3 d1-4=1-4 d1-5=1-2-5 d1-6=1-4-6
2 d2-1=2-1 d2-3=2-3 d2-4=2-4 d2-5=2-5 d2-6=2-4-6
3 d3-1=3-2-1 d3-2=3-2 d3-4=3-2-4 d3-5=3-2-5 d3-6=3-6
4 d4-1=4-1 d4-2=4-2 d4-3=4-1-3 d4-5=4-2-5 d4-6=4-6
5 d5-1=5-6-3-2-1 d5-2=5-6-3-2 d5-3=5-6-3 d5-4=5-6-3-2-4 d5-6=5-6
6 d6-1=6-3-2-1 d6-2=6-3-2 d6-3=6-3 d6-4=6-3-2-4 d6-5=6-5

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...