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

граф

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

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

Матрица D0:

D0= 0 10 18 8
10 0 16 9 21
16 0 15
7 9 0 12
0 23
15 23 0

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

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

На основании матрицы 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= 0 10 18 8 31
10 0 16 9 21
26 16 0 25 37 15
7 9 25 0 30 12
0 23
15 23 0

На основании матрицы 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= 0 10 18 8 31 33
10 0 16 9 21 31
26 16 0 25 37 15
7 9 25 0 30 12
0 23
41 31 15 40 23 0

На основании матрицы 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= 0 10 18 8 31 20
10 0 16 9 21 21
26 16 0 25 37 15
7 9 25 0 30 12
0 23
41 31 15 40 23 0

На основании матрицы 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= 0 10 18 8 31 20
10 0 16 9 21 21
26 16 0 25 37 15
7 9 25 0 30 12
0 23
41 31 15 40 23 0

На основании матрицы 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= 0 10 18 8 31 20
10 0 16 9 21 21
26 16 0 25 37 15
7 9 25 0 30 12
64 54 38 63 0 23
41 31 15 40 23 0

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

   

Выполненные готовые работы

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.

 
4.58
Miha
Эссе, доклады, рефераты, контрольные, курсовые, семестровые работы; магистерские диссертации и дипломы. Презентации, работы в Фотошоп.