- •Типовой расчет
- •Дискретной математике
- •Содержание
- •Задача 1. Операции над множествами
- •Задача 2. Матрицы отношений
- •Задача 3. Отношения
- •Задача 4. Функции
- •Задача 5. Эквивалентные множества. Мощность
- •Задача 6. Алгебраические структуры
- •Задача 7. Основные понятия по теории графов
- •Задача 13. Кратчайшие пути в графе. Алгоритм Дейкстры
- •Задача 14. Задача коммивояжера
- •Задача 15. Эйлеровы и гамильтоновы графы
- •Задача 16. Эйлеровы циклы. Алгоритм Флёри
- •Задача 17. Планарность графов
- •Задача 18. Раскраска графа
- •Список литературы
Задача 13. Кратчайшие пути в графе. Алгоритм Дейкстры
По заданной матрице весов графа найти величину минимального пути и сам путь от вершины до вершины или по алгоритму Дейкстры.
№1 |
|
|
|
|
|
|
|
№2 |
|
|
|
|
|
|
|
|
5 |
10 |
13 |
|
|
|
|
|
11 |
|
14 |
15 |
|
|
|
|
8 |
9 |
13 |
|
|
|
|
|
13 |
|
|
|
|
|
|
|
5 |
3 |
6 |
|
|
|
|
|
|
|
13 |
|
|
|
|
|
8 |
10 |
|
|
|
7 |
11 |
|
9 |
|
|
|
|
|
|
|
9 |
|
|
|
11 |
10 |
|
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№3 |
|
|
|
|
|
|
|
№4 |
|
|
|
|
|
|
|
|
5 |
8 |
7 |
18 |
|
|
|
|
6 |
8 |
11 |
10 |
|
|
|
|
11 |
|
|
|
|
|
|
|
|
9 |
7 |
15 |
|
|
|
|
|
|
17 |
|
|
|
8 |
|
7 |
14 |
11 |
|
|
10 |
12 |
|
6 |
|
|
|
|
|
|
|
6 |
7 |
|
|
7 |
8 |
|
|
11 |
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№5 |
|
|
|
|
|
|
|
|
№6 |
|
|
|
|
|
|
|
|
|
|
11 |
15 |
7 |
|
|
|
|
|
5 |
6 |
9 |
|
|
|
|
|
|
|
|
14 |
18 |
|
|
|
|
|
|
3 |
|
14 |
|
|
|
9 |
|
13 |
7 |
11 |
22 |
|
|
|
3 |
|
3 |
4 |
16 |
|
|
|
|
|
|
|
11 |
16 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
8 |
23 |
|
|
|
|
|
3 |
|
8 |
|
|
|
|
|
|
|
|
19 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
№7 |
|
|
|
|
|
|
|
№8 |
|
|
|
|
|
|
|
|
7 |
9 |
|
11 |
|
|
|
|
7 |
15 |
|
14 |
|
|
|
|
|
6 |
|
13 |
|
|
|
|
7 |
16 |
|
|
|
|
6 |
|
5 |
6 |
|
|
|
|
|
|
19 |
|
21 |
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
17 |
|
|
4 |
|
6 |
|
8 |
|
|
|
13 |
14 |
15 |
|
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№9 |
|
|
|
|
|
|
|
№10 |
|
|
|
|
|
|
|
|
|
10 |
12 |
|
|
|
|
|
|
7 |
19 |
20 |
|
15 |
|
|
|
|
11 |
9 |
|
19 |
|
|
|
|
|
11 |
6 |
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
6 |
9 |
|
16 |
|
|
|
13 |
|
11 |
10 |
|
|
|
|
|
|
|
8 |
13 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
5 |
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№11 |
|
|
|
|
|
|
|
№12 |
|
|
|
|
|
|
|
|
7 |
2 |
|
13 |
|
|
|
|
10 |
11 |
6 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
13 |
8 |
11 |
17 |
|
|
2 |
|
1 |
3 |
11 |
|
|
|
|
|
5 |
6 |
15 |
|
|
|
|
|
|
5 |
|
|
|
|
|
|
7 |
|
|
|
|
|
3 |
|
5 |
|
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№13 |
|
|
|
|
|
|
|
№14 |
|
|
|
|
|
|
|
|
6 |
|
9 |
12 |
|
|
|
|
4 |
9 |
8 |
|
|
|
|
|
6 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
3 |
|
|
4 |
8 |
|
6 |
14 |
|
|
|
2 |
4 |
|
6 |
|
|
|
7 |
5 |
|
|
10 |
|
|
|
2 |
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№15 |
|
|
|
|
|
|
|
|
№16 |
|
|
|
|
|
|
|
|
5 |
|
10 |
8 |
12 |
|
|
|
|
6 |
9 |
13 |
12 |
|
|
|
|
7 |
|
4 |
9 |
|
|
|
|
|
5 |
9 |
6 |
|
|
|
|
|
5 |
|
6 |
11 |
|
|
|
|
|
6 |
|
15 |
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
8 |
9 |
|
|
|
6 |
|
|
13 |
21 |
|
|
|
|
|
|
|
8 |
|
|
|
|
8 |
|
|
9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№17 |
|
|
|
|
|
|
|
№18 |
|
|
|
|
|
|
|
|
8 |
10 |
|
|
|
|
|
|
11 |
14 |
|
|
|
|
|
|
10 |
9 |
12 |
|
|
|
|
|
8 |
10 |
15 |
|
|
|
|
|
10 |
12 |
7 |
|
|
|
|
|
11 |
16 |
20 |
|
|
|
|
|
9 |
13 |
|
|
|
|
|
|
|
12 |
|
|
|
|
|
|
11 |
|
|
|
|
|
11 |
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№19 |
|
|
|
|
|
|
|
№20 |
|
|
|
|
|
|
|
|
|
9 |
7 |
13 |
|
|
|
|
|
|
9 |
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
11 |
5 |
10 |
|
|
|
5 |
|
|
|
|
|
|
|
4 |
|
3 |
6 |
7 |
|
|
|
6 |
7 |
|
8 |
10 |
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
12 |
|
|
|
|
|
7 |
|
5 |
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№21 |
|
|
|
|
|
|
|
№22 |
|
|
|
|
|
|
|
|
4 |
8 |
|
|
|
|
|
|
5 |
4 |
|
10 |
|
|
|
|
|
3 |
|
10 |
|
|
|
|
|
8 |
|
13 |
|
|
3 |
|
4 |
3 |
|
|
|
|
6 |
|
5 |
8 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
8 |
|
|
2 |
|
5 |
|
7 |
|
|
|
|
|
4 |
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№23 |
|
|
|
|
|
|
|
№24 |
|
|
|
|
|
|
|
|
12 |
10 |
|
11 |
|
|
|
|
15 |
10 |
|
|
|
|
|
|
|
10 |
7 |
15 |
|
|
|
|
|
|
12 |
18 |
|
|
8 |
|
7 |
10 |
|
|
|
|
10 |
|
9 |
12 |
19 |
|
|
|
|
|
|
11 |
|
|
|
|
|
|
|
13 |
|
|
|
|
6 |
|
12 |
|
|
|
|
|
11 |
|
14 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
№25 |
|
|
|
|
|
|
|
|
|
|
7 |
12 |
|
10 |
|
|
|
|
|
|
6 |
13 |
|
|
|
5 |
|
4 |
5 |
6 |
|
|
|
|
|
|
|
|
4 |
|
|
|
|
8 |
|
5 |
9 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|