Условие:
Дана транспортная сеть. Определить кратчайшие расстояния по сети от каждой точки (вершины) до всех остальных и соответствующие пути, по которым они проходят.
Решение:
─────────────────────────────
- Формулировка задачи и исходные данные
Предположим, что транспортная сеть задана в виде графа:
• Вершины – точки (узлы) сети.
• Рёбра – маршруты между точками, каждому из которых приписан вес (расстояние, время или стоимость).
Наша задача – для каждой пары вершин найти:
– кратчайшее расстояние
– последовательность вершин (маршрут), по которому это расстояние достигается
───────────────────────────── - Выбор алгоритма
Для решения задачи «все пары кратчайших п...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи