從任意節點到另一個節點找到最短路徑（長度和實際路徑）的遞歸和動態規劃算法

Question

我希望對以下問題有所幫助/指導，我正在努力解決這個問題。 如果您對重新提出問題有任何建議，請留下評論，我會繼續並改變它。

取加權有向無環圖。 （a）找到從節點x到節點t的最短路徑的遞歸算法（算法應該嘗試所有出邊並決定繼續進行）。

I was thinking something along the lines of breadth first search? 
Maybe, another way, a recursive form of dijkstras? However, I'm having 
difficulty thinking of a recursive way to do this. 

（b）作出遞歸算法的迭代動態規劃版本，並註明你是怎麼找到的實際路徑（而不是路徑的只是長度）。

The difference here would obviously be that it is iterative. I'm also 
guessing we would have to keep track of the length of the path/the 
path itself (the nodes) in an array, and refer to it as we iterate. 

Answer 1

設w(i,j)是i之間的邊緣的權重至j，對於任何給定的邊緣(i,j)。可以表示

遞歸關係，可以找到最短路徑爲：

D(u,u) = 0 
D(u,v) = min{ D(u,i) + w(i,v) | for each node i such that the edge (i,v) exists } 

的最短路徑，然後通過D(x,t)表示。

請注意，如果存在負循環 - 該算法將陷入無限循環（因爲此循環的D(u,i) = -infinity），所以爲了正確性，我們必須假定不存在這樣的循環。

這個關係的迭代動態規劃實現基本上是Bellman-Ford algorithm。