Алгоритм поиска кратчайшего пути Dijkstra с краем стоится
У меня есть направленный, положительный взвешенный график. Каждый край имеет стоимость использования. У меня есть только деньги, я хочу вычислить кратчайшие пути с dijkstra алгоритмом, но сумма граничных затрат на маршруте должна быть меньше или равна A.
Я хочу сделать это с большей частью самой маленькой модификации Dijstra (если я могу сделать это с маленькой модификацией Dijkstra). Я должен выполнить в этом O(n*log(n)) если я могу, но я думаю, что могу.
Кто-либо может помочь мне с этим?
2 ответа
https://www.spoj.pl/problems/ROADS/
Проблема была задана на CEOI '98 и его официальное решение можно найти здесь .
Вам действительно не нужно изменять алгоритм Дейкстры, чтобы сделать это, поскольку ответ эквивалентен поиску кратчайшего пути и его последующему принятию, если он меньше или равно A.
Конечно, вы всегда можете замкнуть внутренний цикл, если вы посетите путь со стоимостью более A.
РЕДАКТИРОВАТЬ: С пояснением, что вы хотите минимизировать стоимость И расстояние, вы можете ' Не делайте этого, не уточняя, какое решение вы хотите. Хотите самый дешевый путь? Хотите кратчайший путь? Вам нужна функция стоимости и расстояния? Все они определяют, какую весовую функцию вы должны использовать для конкретного ребра.