Такие алгоритмы, как алгоритм Беллмана-Форда и алгоритм Дейкстры, существуют для поиска кратчайшего пути от одной начальной вершины графа до любой другой вершины. Однако в программе, которую я пишу, начальная вершина меняется гораздо чаще, чем конечная. Какой алгоритм выполняет обратное действие, т. е. при наличии единственной вершины назначения находит кратчайший путь из каждой начальной вершины?
Алгоритм типа Беллмана-Форда, только для многократного запуска, одного пункта назначения?
comment
Также рассмотрите возможность использования алгоритма Роя-Флойда, если ваши узлы сильно меняются.
- person IVlad schedule 28.02.2015
Ответы (2)
Просто переверните все ребра и обработайте пункт назначения как начальный узел. Задача решена.
person
Pham Trung
schedule
27.02.2015
Не могу поверить, что я не подумал об этом. Я попробую и, возможно, отмечу ваш ответ как принятый (поскольку вы ответили первым). Спасибо!
- person flarn2006; 27.02.2015
потрясающий ОТВЕТ :)))
- person DmitrySemenov; 21.04.2018
Если это неориентированный граф: я думаю, что обращение проблемы даст вам преимущества. Просмотрите фактический пункт назначения в качестве начала и найдите кратчайший путь от него до всех остальных узлов в графе. Делая это, вы можете использовать традиционные алгоритмы пути.
person
Andrew_CS
schedule
27.02.2015
Формулируя это таким образом (вместо того, чтобы переворачивать края), предполагается, что расстояние симметрично (что может быть хорошо, просто нужно помнить об этом)
- person harold; 27.02.2015
@harold Это было бы правдой, если бы ребра были взвешены - я не предполагал, что будут веса ребер, поскольку в ОП они не упоминались.
- person Andrew_CS; 28.02.2015
