Построить сетевой график, установить кратчайшие пути и найти расстояние от x1 до всех узлов сети: x12=9; x13=5; x14=5; x29=7; x26=10; x32=8; x36=10; x35=8; x43=9; x45=4; x48=11; x37=9; x58=7; x65=9; x67=27; x69=6; x79=9; x7,10=6; x87=11; x8,10=6; x9,10=7.
Решение
Построим сетевой график по исходным данным:
Найдем кратчайшее расстояние от узла 1 к узлу 10.
Придадим вершине 10 оценку 0.
Вычислим оценки для всех вершин:
для 9: 0+7=7
7: min{7+9=16, 0+6=6}=6
8: min{6+11=17, 0+6=6}=6
5: 6+7=13
6: min{7+6=13, 6+27=33, 13+9=22}=13
2: min{7+7=14, 13+10=23}=14
3: min{14+8=22, 13+10=23, 6+9=15, 13+8=21}=15
4: min{15+9=24, 13+4=17, 6+11=17}=17
1: min{14+9=23, 15+5=20, 17+5=22}=20
41967151956434001872615188023400624840188023500
Таким образом, кратчайший путь 1→3→7→10 равен 20.
Найдем кратчайшее расстояние от узла 1 к узлу 9.
Придадим вершине 9 оценку 0.
Вычислим оценки для всех вершин:
для 7: 0+9=9
8: 9+11=20
5: 20+7=27
6: min{0+6=6, 9+27=36, 27+9=36}=6
2: min{0+7=7, 6+10=16}=7
3: min{7+8=15, 6+10=16, 9+9=18, 27+8=35}=15
4: min{15+9=24, 27+4=31, 20+11=31}=31
1: min{7+9=16, 15+5=20, 37+5=42}=16
235839041655900107251553086000
Таким образом, кратчайший путь 1→2→9 равен 16.
Найдем кратчайшее расстояние от узла 1 к узлу 7.
Придадим вершине 7 оценку 0.
Вычислим оценки для всех вершин:
для 8: 0+11=11
5: 11+7=18
6: min{0+27=27, 18+9=27}=27
2: 27+10=27
3: min{37+8=45, 27+10=37, 0+9=9, 18+8=26}=9
4: min{9+9=18, 18+4=22, 11+11=22}=18
1: min{37+9=46, 9+5=14, 18+5=23}=14
20726401623061001053465169926000
Таким образом, кратчайший путь 1→3→7 равен 14.
Найдем кратчайшее расстояние от узла 1 к узлу 8.
Придадим вершине 8 оценку 0.
Вычислим оценки для всех вершин:
для 5: 0+7=7
6: 7+9=16
2: 15+10=25
3: min{25+8=33, 15+10=25, 7+8=15}=15
4: min{15+9=24, 7+4=11, 0+11=11}=11
1: min{25+9=34, 15+5=20, 11+5=16}=16
15678143034030001148716174815400340614020910540015678162014855001062991172910400
Таким образом, кратчайший путь 1→4→8 равен 16,
кратчайший путь 1→4→5→8 равен 16.
Найдем кратчайшее расстояние от узла 1 к узлу 5.
Придадим вершине 5 оценку 0.
Вычислим оценки для всех вершин:
для 6: 0+9=9
2: 9+10=19
3: min{19+8=27, 9+10=19, 0+8=8}=8
4: min{8+9=17, 0+4=4}=4
1: min{19+9=28, 8+5=13, 4+5=9}=9
5962651832610001129664211836000
Таким образом, кратчайший путь 1→4→5 равен 9.
Найдем кратчайшее расстояние от узла 1 к узлу 6.
Придадим вершине 6 оценку 0.
Вычислим оценки для всех вершин:
для 2: 0+10=10
3: min{10+8=18, 0+10=10}=10
4: 10+9=19
1: min{10+9=19, 10+5=15, 19+5=24}=15
21107401076324001072515159067500
Таким образом, кратчайший путь 1→3→6 равен 15.
Найдем кратчайшее расстояние от узла 1 к узлу 2.
Придадим вершине 2 оценку 0.
Вычислим оценки для всех вершин:
для 3: 0+8=8
4: 8+9=17
1: min{0+9=9, 8+5=13, 17+5=22}=9
105346538608000
Таким образом, кратчайший путь 1→2 равен 9.
Найдем кратчайшее расстояние от узла 1 к узлу 3.
Придадим вершине 3 оценку 0.
Вычислим оценки для всех вершин:
для 4: 0+9=9
1: min{0+5=5, 9+5=14}=5
111950532766000
Таким образом, кратчайший путь 1→3 равен 5.
Найдем кратчайшее расстояние от узла 1 к узлу 2.
106299026733500
Получили кратчайший путь 1→4, равный 5.
Задать вопрос
на новый заказ в Автор24.
