Задание 4: Формальные описания реальных объектов и процессов

Типичная формулировка: «Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице».

Особенности:

• таблица квадратная, строки и столбцы соответствуют одним и тем же пунктам;
• таблица симметрична: расстояние из A в B равно расстоянию из B в A;
• если между двумя пунктами прямой дороги нет, соответствующая клетка пустая;
• диагональ (расстояние пункта до самого себя) всегда пустая.

…

• Граф — набор вершин (пунктов) и рёбер (дорог), соединяющих некоторые пары вершин.
• Вес ребра — числовая характеристика связи, в данных задачах — расстояние в километрах.
• Путь — последовательность рёбер, соединяющая начальную и конечную вершину, где каждое следующее ребро начинается в вершине, где закончилось предыдущее.
• Длина пути — сумма весов всех рёбер, входящих в путь: $S = w_1 + w_2 + \dots + w_n$.
• Симметричность таблицы расстояний: если в ячейке на пересечении строки $X$ и столбца $Y$ стоит число $d$, то и в ячейке на пересечении строки $Y$ и столбца $X$ стоит то же число $d$.
• Отсутствие ребра: пустая клетка означает, что прямой дороги между этими пунктами нет, а не что расстояние равно нулю.
• Кратчайший путь — путь с минимальной суммой весов среди всех возможных путей между двумя вершинами; он может состоять не из одного, а из нескольких промежуточных участков.
• Кратчайший путь по весу и путь с минимальным количеством переходов — разные понятия: путь через две дороги может быть короче одной длинной прямой дороги.

1. Выписать все пункты (вершины) и обозначить начальный и конечный пункт из условия.
2. Построить схему (граф) по таблице: для каждой непустой ячейки нарисовать ребро между соответствующими вершинами и подписать его вес.
3. Проверить построенный граф на симметричность — сверить, что каждое ребро отражено согласованно в обеих клетках таблицы.
4. Найти все вершины, напрямую соединённые с начальным пунктом, и вершины, напрямую соединённые с конечным пунктом.
5. Перебрать все возможные маршруты от начала до конца (через одну, две и более промежуточных вершин), не повторяя вершины в одном маршруте.
6. Для каждого маршрута посчитать сумму весов рёбер.
7. Сравнить все полученные суммы и выбрать наименьшую — это и есть ответ.
8. Сверить ответ: убедиться, что при движении по выбранному маршруту действительно используются только существующие дороги.