#algorithm #data-structures #graph #shortest-path #dijkstra
#алгоритм #структуры данных #График #кратчайший путь #dijkstra
Вопрос:
Учитывая неориентированный граф, который имеет обычные ребра и определенные ребра, наша цель-найти сумму веса кратчайшего пути между двумя вершинами(от начальной вершины до конечной вершины), только пройдя через определенное ребро, равное или меньшее, чем один раз. Другими словами, существует несколько определенных ребер, и можно использовать не более одного из них.
Это проблема, с которой я столкнулся в своей домашней работе по структуре данных, и я остановился на первом шаге на пути к хранению весов ребра в графике. Поскольку в графике есть два вида ребер, я понятия не имею, как решить эту проблему.
Я знаю, что могу получить кратчайший путь с помощью алгоритма Дейкстры, но во время процесса, как я могу изменить алгоритм в соответствии с требованиями ограничения?
Большое спасибо, что ответили на мой вопрос!
Комментарии:
1. «проходите только через определенный край, равный или меньший, чем один раз» : мне это непонятно. Означает ли это, что существует несколько определенных ребер, и только самое большее одно из них может быть использовано, или это означает, что ни одно из специальных ребер не может быть использовано более одного раза. Я полагаю, что это первое, но оно плохо сформулировано.
2. @trincot Это первое, о чем вы упомянули, я изменю свой вопрос, чтобы он был более четким, большое спасибо!
Ответ №1:
Решение состоит в том, чтобы дублировать график следующим образом:
- Дублируйте вершины таким образом, чтобы для каждой исходной вершины A у вас были A и A’.
- Если в исходном графике есть нормальное ребро между A и B, то в новом графике поместите ребро между A и B, а также между A’ и B’
- Если в исходном графике есть определенное ребро между A и B, то в новом графике поместите (направленное) ребро от A до B’ (не обратное!) и от B до A’ (опять же: не обратное!). Эти края должны быть направлены.
Если теперь задача состояла в том, чтобы найти кратчайший путь между S и D, то решите в новом графике задачу нахождения кратчайшего пути между S и D или S и D’, который когда-либо был самым коротким. Для этого вы можете использовать стандартную реализацию алгоритма Дейкстры, начиная с S и заканчивая, когда вы найдете либо D, либо D’.
Комментарии:
1. О, я думаю, что понимаю смысл, но если график неориентирован, должен ли я добавить новое ребро между Aamp;B’ и A’amp;B?
2. Я обновил свой ответ, чтобы сделать некоторые аспекты более ясными.
3. Я думаю, что, вероятно, понимаю смысл. Но почему описанная выше процедура может гарантировать, что будет использоваться не более одного конкретного ребра?
4. Да, потому что после посещения «акцентированного» узла невозможно вернуться к узлам без акцента.
5. Спасибо за ваш полезный ответ! Я думаю, что я полностью осознал!
Ответ №2:
Учитывая n конкретные ребра, время поиска Дейкстры n увеличивается.
При каждом запуске одному из n узлов (назовем его узлом i ) должен быть установлен его реальный вес, а всем остальным n-1 узлам-бесконечное значение. В конце каждого прогона сохраняйте кратчайший путь и шаг i
В конце всех запусков выберите из сохраненных путей самый короткий.
set all n edges weight to infinity for i=0; i lt; n ; i { set edge i to it real weight run run Dijkstra's search store path set all n edges weight to infinity } select the shortest path from the stored paths.