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

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

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

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

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

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

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

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

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

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 имеет постоянную пометку

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

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

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 имеет постоянную пометку

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, делаем её пометку постоянной

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 имеет постоянную пометку

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 имеет постоянную пометку