Дан ориентированный граф, состоящий из десяти вершин и ребер, соединяющих вершины между собой. Известен. 2

Дан ориентированный граф, состоящий из десяти вершин и ребер, соединяющих вершины между собой. Известен вес каждого ребра (длина). Требуется найти кратчайший путь от источника до стока графа. Вариант 3 10 4 7 5 9 1 6 8 2 3 10 12 8 3 2 12 6 10 5 3 4 8 6 15 10 11 2 10 4 7 5 9 1 6 8 2 3 10 12 8 3 2 12 6 10 5 3 4 8 6 15 10 11 2

В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞
3 ∞
4 ∞
5 ∞
6 ∞
7 ∞
8 ∞
9 ∞
10 ∞
Итерация 1:
D(x1) = {x2; x3; x4}
l(x2) = min{l(x2); l(x1) + c(x1; x2)} = min{∞; 10}= 10
l(x3) = min{l(x3); l(x1) + c(x1; x3)} = min{∞; 12}= 12
l(x4) = min{l(x4); l(x1) + c(x1; x4)} = min{∞; 8}= 8
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10
3 ∞ 12
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞
6 ∞ ∞
7 ∞ ∞
8 ∞ ∞
9 ∞ ∞
10 ∞ ∞
Итерация 2:
D(x4) = {x5; x7}
l(x5) = min{l(x5); l(x4) + c(x4; x5)} = min{∞; 8+6}= min{∞; 14}= 14
l(x7) = min{l(x7); l(x4) + c(x4; x7)} = min{∞; 8+10}= min{∞; 18}= 18
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10 10+ 10+ 10+ 10+ 10+ 10+ 10+ 10+
3 ∞ 12 12
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞ 14
6 ∞ ∞ ∞
7 ∞ ∞ 18
8 ∞ ∞ ∞
9 ∞ ∞ ∞
10 ∞ ∞ ∞
Итерация 3:
D(x2) = {x4; x5}
l(x4) = min{l(x4); l(x2) + c(x2; x4)} = min{8; 10+3}= min{8; 13}= 8
l(x5) = min{l(x5); l(x2) + c(x2; x5)} = min{14; 10+2}= min{14; 12}= 12
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10 10+ 10+ 10+ 10+ 10+ 10+ 10+ 10+
3 ∞ 12 12 12+ 12+ 12+ 12+ 12+ 12+ 12+
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞ 14 12
6 ∞ ∞ ∞ ∞
7 ∞ ∞ 18 18
8 ∞ ∞ ∞ ∞
9 ∞ ∞ ∞ ∞
10 ∞ ∞ ∞ ∞
Итерация 4:
D(x3) = {x4; x6}
l(x4) = min{l(x4); l(x3) + c(x3; x4)} = min{8; 12+2}= min{8; 14}= 8
l(x6) = min{l(x6); l(x3) + c(x3; x6)} = min{∞; 12+12} = min{∞; 24}= 24
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10 10+ 10+ 10+ 10+ 10+ 10+ 10+ 10+
3 ∞ 12 12 12+ 12+ 12+ 12+ 12+ 12+ 12+
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞ 14 12 12+ 12+ 12+ 12+ 12+ 12+
6 ∞ ∞ ∞ ∞ 24
7 ∞ ∞ 18 18 18
8 ∞ ∞ ∞ ∞ ∞
9 ∞ ∞ ∞ ∞ ∞
10 ∞ ∞ ∞ ∞ ∞
Итерация 5:
D(x5) = {x7; x8}
l(x7) = min{l(x7); l(x5) + c(x5; x7)} = min{18; 12+5}= min{18; 17}= 17
l(x8) = min{l(x8); l(x5) + c(x5; x8)} = min{∞; 12+3}= min{∞; 15}= 15
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10 10+ 10+ 10+ 10+ 10+ 10+ 10+ 10+
3 ∞ 12 12 12+ 12+ 12+ 12+ 12+ 12+ 12+
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞ 14 12 12+ 12+ 12+ 12+ 12+ 12+
6 ∞ ∞ ∞ ∞ 24 24
7 ∞ ∞ 18 18 18 17
8 ∞ ∞ ∞ ∞ ∞ 15+ 15+ 15+ 15+ 15+
9 ∞ ∞ ∞ ∞ ∞ ∞
10 ∞ ∞ ∞ ∞ ∞ ∞
Итерация 6:
D(x8) = {x10}
l(x10) = min{l(x10); l(x8) + c(x8; x10)} = min{∞; 15+10}= min{∞; 25}= 25
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10 10+ 10+ 10+ 10+ 10+ 10+ 10+ 10+
3 ∞ 12 12 12+ 12+ 12+ 12+ 12+ 12+ 12+
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞ 14 12 12+ 12+ 12+ 12+ 12+ 12+
6 ∞ ∞ ∞ ∞ 24 24 24
7 ∞ ∞ 18 18 18 17 17+ 17+ 17+ 17+
8 ∞ ∞ ∞ ∞ ∞ 15+ 15+ 15+ 15+ 15+
9 ∞ ∞ ∞ ∞ ∞ ∞ ∞
10 ∞ ∞ ∞ ∞ ∞ ∞ 25
Итерация 7:
D(x7) = {x8; x9; x10}
l(x8) = min{l(x8); l(x7) + c(x7; x8)} = min{15; 17+8}= min{15; 25}= 15
l(x9) = min{l(x9); l(x7) + c(x7; x9)} = min{∞; 17+6}= min{∞; 23}= 23
l(x10) = min{l(x10); l(x7) + c(x7; x10)} = min{25; 17+15}= min{25; 32}= 25
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10 10+ 10+ 10+ 10+ 10+ 10+ 10+ 10+
3 ∞ 12 12 12+ 12+ 12+ 12+ 12+ 12+ 12+
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞ 14 12 12+ 12+ 12+ 12+ 12+ 12+
6 ∞ ∞ ∞ ∞ 24 24 24 24
7 ∞ ∞ 18 18 18 17 17+ 17+ 17+ 17+
8 ∞ ∞ ∞ ∞ ∞ 15+ 15+ 15+ 15+ 15+
9 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 23+ 23+ 23+
10 ∞ ∞ ∞ ∞ ∞ ∞ 25 25
Итерация 8:
D(x9) = {x10}
l(x10) = min{l(x10); l(x9) + c(x9; x10)} = min{17; 23+11}= min{25; 34}= 25
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10 10+ 10+ 10+ 10+ 10+ 10+ 10+ 10+
3 ∞ 12 12 12+ 12+ 12+ 12+ 12+ 12+ 12+
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞ 14 12 12+ 12+ 12+ 12+ 12+ 12+
6 ∞ ∞ ∞ ∞ 24 24 24 24 24+ 24+
7 ∞ ∞ 18 18 18 17 17+ 17+ 17+ 17+
8 ∞ ∞ ∞ ∞ ∞ 15+ 15+ 15+ 15+ 15+
9 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 23+ 23+ 23+
10 ∞ ∞ ∞ ∞ ∞ ∞ 25 25 25
Итерация 9:
D(x6) = {x7}
l(x7) = min{l(x7); l(x6) + c(x6; x7)} = min{17; 24+4}= min{17; 28}= 17
В\И I(0) I(1) I(2) I(3) I(4) I(5) I(6) I(7) I(8) I(9)
1 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+
2 ∞ 10 10+ 10+ 10+ 10+ 10+ 10+ 10+ 10+
3 ∞ 12 12 12+ 12+ 12+ 12+ 12+ 12+ 12+
4 ∞ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+ 8+
5 ∞ ∞ 14 12 12+ 12+ 12+ 12+ 12+ 12+
6 ∞ ∞ ∞ ∞ 24 24 24 24 24+ 24+
7 ∞ ∞ 18 18 18 17 17+ 17+ 17+ 17+
8 ∞ ∞ ∞ ∞ ∞ 15+ 15+ 15+ 15+ 15+
9 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 23+ 23+ 23+
10 ∞ ∞ ∞ ∞ ∞ ∞ 25 25 25 25+
Путь от х1 до х10, длина равна 25:
D-1(x10) = {x7; x8; x9} [25]
l(x10) = l(x7) + c(x7; x10) = 17+15 = 32 ≠ 25
l(x10) = l(x8) + c(x8; x10) = 15+10 = 25= 25
l(x10) = l(x9) + c(x9; x10) = 23+11 = 34 ≠ 25
x8→ x10
D-1(x8) = {x5; x7} [15]
l(x8) = l(x5) + c(x5; x8) = 12+3 = 15 =15
l(x8) = l(x7) + c(x7; x8) = 17+8 = 25 ≠ 15
x5→ x8→ x10
D-1(x5) = {x2; x4} [12]
l(x5) = l(x2) + c(x2; x5) = 10+2 = 12 =12
l(x5) = l(x4) + c(x4; x5) = 8+6 = 14 ≠ 12
x2→ x5→ x8→ x10
D-1(x2) = {x1} [10]
l(x1) = l(x1) + c(x1; x2) = 0+10 = 10 =10
x1→ x2→ x5→ x8→ x10
Следовательно, самым коротким является следующий путь:
10
4
7
5
9
1
6
8
2
3
10
12
8
3
2
12
6
10
5
3
4
8
6
15
10
11
2
10
4
7
5
9
1
6
8
2
3
10
12
8
3
2
12
6
10
5
3
4
8
6
15
10
11
2
Длиной в 25 единиц
Работа №7 «Максимальный поток на графе»