"На рисунке схема дорожек парка им. Кинга изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорожек (в метрах). Так как таблицу и схему…
"На рисунке схема дорожек парка им. Кинга изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорожек (в метрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация памятников в таблице никак не связана с буквенными обозначениями на графе.Определите длину кратчайшего пути между пунктами A и K (при условии, что передвигаться можно только по построенным дорогам). "
Привет! Давай разберёмся по шагам, как подойти к этой задаче.
Подсказка 1
- Обрати внимание на узлы F и K: у них по две дороги. Это зафиксированная особенность, которая поможет понять, какие ребра должны выходить из F и из K. Попробуй подобрать такие номера дорог (P1…P8) для F и для K, чтобы из каждого из них была ровно одна прямого выхода к другим узлам, и чтобы граф в итоге получился связным.
Подсказка 2
- После того как найдёшь разумное сопоставление дорог F и K с двумя соседами, остальные дороги можно «поставить» так, чтобы все узлы связались в одну карту (и каждый номер дороги используется один раз). Это и есть решение методом подбора.
Подсказка 3
- Когда граф сопоставлен с конкретными длинами дорог (через номера P1…P8), чтобы найти кратчайший путь от A до K, можно применить обычный алгоритм кратчайшего пути (Дейкстра/буферный обход), и затем сложить длины ребер along этого пути. В правильном сопоставлении путь A–K даст искомую длину.
Если хочешь, могу привести конкретный вариант сопоставления P1…P8 к ребрам и посчитать кратчайший путь по твоей таблице — и объясню каждый шаг. Также можешь попробовать сам(а) и прислать свой вариант, чтобы мы вместе разобрали.
Пожалуйста, оцени мой ответ лайком или дизлайком.
