Неориентированный взвешенный граф задан списком рёбер с весами: A–B: 4, A–C: 2, B–C: 1, B–D: 5, C–D: 8, C–E: 10, D–E: 2, D–F: 6, E–F: 3. Чему равна наименьшая суммарная длина пути из вершины A в вершину F?
Показать ответ и разборСкрыть ответ и разбор
Верный ответ
- A13
Разбор
Применим алгоритм Дейкстры. Из A: до C расстояние 2, до B расстояние 4. Через C до B получается 2 + 1 = 3, это лучше, чем 4, поэтому B = 3. До D: через B 3 + 5 = 8, через C 2 + 8 = 10, значит D = 8. До E: через D 8 + 2 = 10, через C 2 + 10 = 12, значит E = 10. До F: через E 10 + 3 = 13, через D 8 + 6 = 14, значит F = 13. Кратчайший путь A–C–B–D–E–F имеет длину 13. Вариант «14» получается при пути A–C–B–D–F, вариант «15» при пути A–B–D–F, вариант «18» при пути A–B–C–E–F.