Похоже, вы работаете с графиком, где узлы являются точками на 2D-сетке, и каждый узел имеет направленный край к узлу над ним, а другой - к узлу справа.
Я не думаю, что здесь будет работать только алгоритм Дейкстры. Он находит один дешевый путь затрат, и нет способа изменить его, чтобы найти все кратчайшие пути.
Поскольку это такой специальный граф (то есть направленный и ацикличный), вы можете вычислить количество самых дешевых путей, если вы знаете, что такое стоимость самого дешевого пути, используя простой повтор. Обратите внимание на то, что
number_paths(i,j)=number_of_paths(i-1,j)+number_of_paths(i,j-1)
т.е. число путей из любого узла является суммой, что из приведенных выше и справа узлов. (Это исключает базовые случаи, когда текущий узел является пунктом назначения и где узел назначения недоступен для текущего узла.)
Единственное, что нужно, это изменить это, чтобы считать только самые дорогие пути. Теперь мы уже знаем, что самый дешевый путь имеет некоторую стоимость X. Мы можем использовать его для увеличения нашего повторения, чтобы он учитывал только самый дешевый путь. На стартовом узле мы знаем, что стоимость оставшегося пути равна X. От любого из соседних узлов к стартовому узлу (т. Е. Из узлов непосредственно выше и справа от него), следовательно, стоимость Xe, где e - стоимость края между этими узлами. Это правило применяется к любому узлу, где известны затраты на достижение текущего узла. Таким образом, мы знаем, что мы прошли самый дешевый путь, когда мы достигли целевого узла, а значение этого узла равно 0 (т. Е. Мы вычтем все затраты на ребра, которые образуют самый дешевый путь).
Таким образом, мы можем просто увеличить нашу повторяемость, чтобы мы сохранили 3 значения вместо 2, координаты и оставшуюся стоимость пути (по существу, превращаясь в ту же задачу для 3D-графика, где 3-е измерение является стоимостью). Начальный узел имеет вид (x_start,y_start,cost), целевой узел имеет вид (x_end,y_end,0). Наше повторение будет выглядеть так:
paths(x,y,cost_left)=
0 if x_end,y_end is unreachable from x,y or cost_left<0
1 if x==X-end and y==y_end and cost_left==0
paths(x-1,y,cost_left-edge(x,y,x-1,y))+paths(x,y-1,cost_left-edge(x,y,x,u-1)) otherwise
Сложность алгоритма должны быть O (п м C), где п и т являются размерами сетки и C является стоимостью самого дешевого пути.
Привет, Вы правильно поняли вопрос, хотя я забыл упомянуть, что вы можете только идите направо и вверх. Я не понял, что должен содержать ваш список предшественников. Кроме того, вы упомянули, используя алгоритм динамического программирования, чтобы подсчитать количество путей с длиной, равной кратчайшему пути, и это именно то, что мне трудно понять, как это сделать. Любое разъяснение/помощь будут оценены. – Meir
Добавлено более подробное объяснение того, как рассчитать количество путей. –