Условие:
Построить геодезическое дерево взвешенного графа, заданного множеством вершин
Решение:
Рассмотрим взвешенный граф с вершинами a, b, c, d, e, f и ребрами с весами:
а–b (7), a–c (9), a–f (14),
\tb–c (10), b–d (15),
\tc–d (11),
\td–e (6),
\te–f (9),
\tf–c (2).
Чтобы построить геодезическое дерево (дерево кратчайших путей) с начальной вершиной a, определим кратчайшие расстояния от a до остальных вершин.
- Расстояние до a равно
0.
- Для вершины b: есть ребро a–b с весом 7, других вариантов для уменьшения расстояния нет. Получаем: d(a,b)=7.
- Для вершины c: прямое ребро a–c...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи