Тип 4. Поиск кратчайшего пути. Теория
1. Основные правила
- Весовая матрица (таблица): Сетка с числами, где число на пересечении строки и столбца — это длина дороги между населенными пунктами.
- Симметричность: Таблица симметрична относительно главной диагонали (путь из А в Б равен пути из Б в А).
- Пустой прочерк: Означает, что прямой дороги между пунктами нет.
2. Алгоритм решения
Лучший способ не ошибиться — построить схему (граф) или дерево путей.
- Начните с начальной точки (например, пункт А).
- Выпишите все прямые пути из А в другие пункты.
- Стройте цепочки дальше к конечному пункту (например, D).
- Считайте сумму: Складывайте километраж каждого отрезка.
- Сравнивайте: Если нашли путь длиной 15, а потом нашли 12 — первый можно забыть.
3. Пример
Таблица:
| A | B | C | D | |
|---|---|---|---|---|
| A | 2 | 5 | ||
| B | 2 | 1 | 8 | |
| C | 5 | 1 | 3 | |
| D | 8 | 3 |
Найти кратчайший путь от A до D.
- Путь 1 (прямой через C): 5 + 3 = 8
- Путь 2 (через B и C): 2 + 1 + 3 = 6
- Путь 3 (прямой через B): 2 + 8 = 10
Ответ: 6.
4. На что обратить внимание:
- Промежуточные пункты: Иногда в условии требуют, чтобы путь обязательно проходил через пункт С или, наоборот, не проходил через него.
- Подсказка: Часто самый короткий визуально путь (меньше всего букв) оказывается длиннее по километрам, чем путь с кучей пересадок.
- Совет: Если таблица большая, рисуйте граф в виде точек с линиями — так легче наглядно увидеть все варианты.