Алгоритм Дейкстры

Сентябрь 6, 2022

Главная
Алгебра
Алгоритм Дейкстры

Содержание

2. Задан взвешенный граф с N вершинами и M рёбрами. Для каждого ребра задано его расстояние –
3. Типы пометок вершин отсутствует – не найдено ни одного пути до этой вершины; временная – путь
4. 1 6 7 8 9 10 5 4 3 2 5 2 11 3 17 3
5. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
6. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
7. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
8. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
9. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
10. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
11. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
12. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
13. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
14. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
15. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
16. 1 6 7 8 9 10 5 4 3 2 5 2 12 3 17 3
18. Скачать презентацию

Слайд 2

Задан взвешенный граф с N вершинами и M рёбрами. Для каждого

ребра задано его расстояние – неотрицательная величина. Требуется найти минимальное расстояние от вершины 1 до всех остальных вершин (вариант – минимальное расстояние между заданной парой вершин).

Слайд 3

Типы пометок вершин
отсутствует – не найдено ни одного пути до этой

вершины;
временная – путь найден, но он, возможно, не минимален;
постоянная – найден минимальный путь

Слайд 4

1
6
7
8
9
10
5
4
3
2
5
2
11
3
17
3
24
25
2
4
21
9
7
Исходный граф

Слайд 5

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
Заносим в кучу информацию о начальной вершине 1.
Длина пути до

неё равна нулю

Слайд 6

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
12
5
Извлекаем вершину 1, делаем её пометку постоянной.
Пересчитываем длину пути до вершин

2 и 7

Слайд 7

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
12
5
30
8
Извлекаем вершину 2, делаем её пометку постоянной.
Пересчитываем длину пути до вершин

8 и 9

Слайд 8

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
Извлекаем вершину 8, делаем её пометку постоянной.
Пересчитываем длину пути до вершин

7 и 9

Слайд 9

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
35
Извлекаем вершину 7, делаем её пометку постоянной.
Пересчитываем длину пути до вершины

5

Слайд 10

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
35
Извлечённая вершина 7 имеет постоянную пометку

Слайд 11

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
27
46
Извлекаем вершину 9, делаем её пометку постоянной.
Пересчитываем длину пути до вершин

5 и 6

Слайд 12

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
27
31
Извлекаем вершину 5, делаем её пометку постоянной.
Пересчитываем длину пути до вершины

6

Слайд 13

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
27
31
Извлечённая вершина 9 имеет постоянную пометку

Слайд 14

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
27
31
Извлекаем вершину 6, делаем её пометку постоянной

Слайд 15

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
27
31
Извлечённая вершина 5 имеет постоянную пометку

Слайд 16

1
6
7
8
9
10
5
4
3
2
5
2
12
3
17
3
24
25
2
4
21
9
7
0
11
5
25
8
27
31
Извлечённая вершина 6 имеет постоянную пометку