Как найти путь с максимальной стоимостью

Question

У меня есть ориентированный граф, вершины которого стоят. Я хотел бы найти путь с максимальной стоимостью между двумя вершинами, но я нашел только алгоритмы для решения пути с минимальной стоимостью.

Также я использую Java.

Answer 1

1. Нормализовать все затраты, чтобы минимальная стоимость была больше 0.
2. Измените все расходы на (1 / стоимость).
3. Запуск алгоритма минимальной стоимости.

Полученный путь - это путь максимальной стоимости на исходном графике.

Answer 2

Просто измените функцию оценки используемого алгоритма.Если для кратчайшего пути функция возвращает большее значение для более коротких путей, в вашем случае вы захотите вернуть меньшее значение для более коротких путей.