алгоритм — поиск веса кратчайшего пути в переполнении стека
Я пытаюсь написать код на C ++
который вычисляет приоритет для выбора определенного пути
после расчета он выбирает тот, который имеет наивысший приоритет.
Но у меня есть другой код для кратчайшего пути, который я объединяю с моим кодом
которые выбирают путь с наименьшим весом!
проблема в:
как я могу изменить свой код, дать путь с наивысшим приоритетом, с наименьшим весом!
без изменения знака. (Я не хочу иметь отрицательные числа! «
Решение
Если ваша цель — получить кратчайший путь с самым высоким приоритетом, вы можете представить свой новый вес как 1 / приоритет. Таким образом, ваш алгоритм выберет путь, в котором сумма всех ребер, через которые вы проходите, дает вам высокий приоритет.
Будьте осторожны, чтобы не перепутать проблему с проблема максимальной емкости.
Например, если есть 2 пути от A до B с заданными приоритетами для каждого ребра:
A — 60 -> X1 — 60 -> X2 — 60 -> B
или же
A — 100 -> X1 — 50 -> X2 — 100 -> B
Убедитесь, что вы хотите, чтобы ваш алгоритм выбрал второй путь, где 1/100 + 1/50 + 1/100 = 0,04, но вы проходите границу только с 50 или приоритетом, а не путь, где 1/60 + 1/60 + 1/60 = 0,05, но минимальный приоритет, который вы прошли, имеет значение 60
Другой вариант, если вы знаете наивысший приоритет края MAX_PRIORITY на вашем графике (допустим, он равен 100) и вы не хотите иметь дело с числами с плавающей запятой:
Вы можете представить свой вес как (MAX_PRIORITY + 1 — приоритет) ((101 — приоритет) в примере). Таким образом, у вас не будет отрицательного числа.
Другие решения