Нарисовать свой взвешенный граф из 5 вершин (например, города и расстояния между ними) и найти кратчайший путь от одной вершины до всех остальных по алгоритму Дейкстры, фиксируя метки и предшественников. Посмотреть видео-урок по теме.

Question

Вопрос:

Фото задания

Нарисовать свой взвешенный граф из 5 вершин (например, города и расстояния между ними) и найти кратчайший путь от одной вершины до всех остальных по алгоритму Дейкстры, фиксируя метки и предшественников. Посмотреть видео-урок по теме.

Accepted Answer

Рассмотрим граф из пяти вершин: A, B, C, D, E. Вес рёбер — расстояние между вершинами.

Рёбра графа: AB = 4, AC = 2, BC = 1, BD = 5, CD = 8, CE = 10, BE = 12, DE = 2.

Начальная вершина — A. Обозначение ∞ означает, что путь пока не найден.

Шаг	Зафиксированная вершина	Метки A, B, C, D, E	Предшественники
0	—	0, 4, 2, ∞, ∞	—, A, A, —, —
1	A	0, 4, 2, ∞, ∞	—, A, A, —, —
2	C	0, 3, 2, 10, 12	—, C, A, C, C
3	B	0, 3, 2, 8, 12	—, C, A, B, C
4	D	0, 3, 2, 8, 10	—, C, A, B, D
5	E	0, 3, 2, 8, 10	—, C, A, B, D

Ход алгоритма Дейкстры:

Для A устанавливаем метку 0. Через A получаем: B = 4, C = 2.
Минимальная незакреплённая метка — C = 2. Через C: B = 2 + 1 = 3, D = 2 + 8 = 10, E = 2 + 10 = 12.
Минимальная метка — B = 3. Через B: D = 3 + 5 = 8, поэтому предшественник D — B. Для E получаем 3 + 12 = 15, что хуже значения 12.
Минимальная метка — D = 8. Через D: E = 8 + 2 = 10, поэтому предшественник E — D.
Остаётся E = 10. Все вершины обработаны.

Кратчайшие пути из A:

A → C: длина 2.
A → C → B: длина 2 + 1 = 3.
A → C → B → D: длина 2 + 1 + 5 = 8.
A → C → B → D → E: длина 2 + 1 + 5 + 2 = 10.

Предшественники образуют дерево кратчайших путей: C ← A, B ← C, D ← B, E ← D. Теоретическую часть следует сопоставить с видео-уроком по алгоритму Дейкстры.

Ответ: из вершины A кратчайшие расстояния равны: до C — 2, до B — 3, до D — 8, до E — 10.