Кратчайший путь в графе


Задание:
Пусть дан граф G. Определим кратчайший путь из вершины 1 в вершину 6.
5
2








6
1


3
4

№Вар 1 2 3 4 5 6 7 8 1 9 10 11 12 13 | 14 15
Ребро Длина ребра
1-2 5 2 2 2 2 5 2 2 2 2 5 2 2 2 2
1-3 3 5 3 3 3 3 5 3 3 3 3 5 3 3 3
2-3 1 1 5 1 1 1 1 5 1 1 1 1 5 1 1
2-4 2 2 2 5 2 2 2 2 5 2 2 2 2 5 2
7-5 10 10 10 10 15 10 10 10 10 15 10 10 10 10 15
3-4 8 6 6 6 6 7 6 6 6 6 6 6 6 6 6
3-5 4 8 4 4 4 4 7 4 4 4 4 6 4 4 4
4-5 3 3 8 3 3 3 3 7 3 3 3 3 6 3 3
4-6 8 8 8 10 8 8 8 8 7 8 8 8 8 6 8
5-6 2 2 2 2 5 2 2 2 2 7 ■" 2 2 2 2 6
№Вар 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Ребро Длина ребра
1-2 4 2 2 2 2 4 2 2 2 2 4 2 2 2 2
1-3 3 4 3 1 3 3 4 3 3 3 3 4 3 3 3
2-3 1 1 4 1 1 1 1 4 1 1 1 1 4 1 1
2-4 2 2 2 4 £. 2 2 2 4 2 2 2 2 4 2
2-5 10 10 10 10 !4 10 10 10 10 14 10 10 10 10 14
3-4 8 6 6 6 6 7 6 6 6 6 6 6 6 6 6
3-5 4 8 4 4 4 4 7 4 4 4 4 6 4 4 4
4-5 3 3 8 j3 3 3 7 3 3 3 3 6 3 3
4-6 8 8 8 10 8 8 8 8 7 8 8 8 8 6 8
5-6 2 2 2 2 5 2 2 2 2 7 2 2 2 2 6

Приложенные файлы

  • docx 5416797
    Размер файла: 17 kB Загрузок: 0

Добавить комментарий