Я хочу найти K «кратчайших» путей или, точнее, K путей с минимальными затратами, в очень конкретном графике c, как показано на рисунке. Его функции:
Узлы задаются уровнем lev от 1 до d, с e[lev] узлами по уровню. Добавлены узел источника [0,1] и узел назначения [d+1,1].
От уровня lev-1 до уровня lev существуют все возможные ребра, и стоимость ребра зависит только от конечного узла [lev,j], поэтому его можно обозначить c[lev,j]. Узлы на уровне упорядочены по возрастанию стоимости. Стоимость c[d+1,1] ребра с конечным узлом [d+1,1] равна нулю.
Затраты неотрицательны.
Требуемые пути от источника [0,1] к месту назначения [d+1,1]. Путь с минимальной стоимостью, очевидно, является самым левым: [0,1] -> [1, 1] -> ... -> [d + 1, 1].
На практике типичное значение для d равно 10, а e[lev] составляет около 100 для lev между 1 и d. Максимальный сценарий будет для d=20. Число K требуемых путей составляет несколько сотен.
В первую очередь меня интересует выбор подходящего алгоритма: иены, Эппштейна, Като Хофмана, ... Тогда в идеале я хотел бы использовать существующую реализацию , Конечное использование будет внутри R, так что C, C ++ или Fortran реализации будут работать.