@vitik

Проверте пожалуйста задачу: Воспользовавшись алгоритмом Дейкстры рассчитать минимальный путь от вершины A до всех остальных вершин.


Шаг 1. Вершине А присваиваем 0, всем последующим присваиваем ∞.
Шаг 2. С вершины А возможно попасть в вершины B, C, D. Минимальное расстояние от А до С = 1.
Шаг 3. С вершины С возможно попасть в вершины B, G, F, E. Минимальное расстояние от A до G = 4.
Шаг 3. С вершины G возможно попасть в вершины B, K. Минимальное расстояние от A до D = 4.
Шаг 3. С вершины D возможно попасть в вершины E. Минимальное расстояние от A до E = 6.
Шаг 3. С вершины E возможно попасть в вершины F, K. Минимальное расстояние от A до B = 7.

Ответ. Минимальный путь от вершины A до всех остальных вершин равно:
A → B = 7
A → C = 1
A → D = 4
A → E = 6
A → F = 8
A → G = 4
A → K = 8

Есть сомнения правильно ли, что после последней итерации A → F = 8, A → K = 8

Миниатюры

 

0

@AdmiralHood

А в чём сомнение-то?

0

@vitik

У меня последний шаг находит минимальное расстояние от A до B = 7, после этого от В уже никуда идти. Правильно что я после всего указал A → F = 8, A → K = 8

0

@AdmiralHood

Более короткие пути блокируют более длинные. Если в какую-то точку уже пришли раньше более коротким путём, то длтнному пути в этой точке не место

0