Похоже, вы работаете с графиком, где узлы являются точками на 2D-сетке, и каждый узел имеет направленный край к узлу над ним, а другой - к узлу справа.
Я не думаю, что применение алгоритма Дейкстры здесь сработает. Он находит один самый дешевый путь, и на самом деле нет способа изменить его, чтобы найти все самые короткие пути.
Поскольку это такой специальный граф (то есть направленный и ациклический), вы можете вычислить количество самых дешевых путей, если вы знаете, какова стоимость самого дешевого пути, используя простое повторение. Обратите внимание, что
number_paths(i,j)=number_of_paths(i-1,j)+number_of_paths(i,j-1)
т.е. количество путей от любого узла является суммой пути от узлов выше и справа от него. (Это исключает базовые случаи, когда текущий узел является пунктом назначения, а узел назначения недоступен из текущего узла.)
Единственное, что нужно, это изменить это, чтобы считать только те пути, которые являются самыми дешевыми. Теперь мы уже знаем, что самый дешевый путь имеет некоторую стоимость X. Мы можем использовать его для увеличения нашего повторения, чтобы он учитывал только самый дешевый путь. На начальном узле мы знаем, что стоимость оставшегося пути равна X. От любого из смежных узлов до начального узла (то есть от узлов, расположенных выше и справа от него), поэтому стоимость равна Xe, где e - это стоимость края между этими узлами. Это правило применяется к любому узлу, для которого известна стоимость достижения текущего узла. Таким образом, мы знаем, что прошли самый дешевый путь, когда достигаем узла назначения, и значение этого узла равно 0 (то есть мы вычли все затраты на ребра, которые образуют самый дешевый путь).
Таким образом, мы можем просто увеличить нашу повторяемость, чтобы сохранить 3 значения вместо 2, координаты и оставшуюся стоимость пути (по сути, преобразование в ту же задачу для трехмерного графика, где третье измерение - это стоимость). Начальный узел имеет форму (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 (n m C), где n и m - размеры сетки, а C - стоимость самого дешевого пути.