首页 文章

递归和动态编程算法，用于查找从任意节点到另一个节点的最短路径（长度和实际路径）

提问于
浏览 次
0

我希望在以下问题上提供一些帮助/指导，我正在努力解决这个问题 . 如果您对重新提问有任何建议，请发表评论，我会继续进行更改 .

采用加权有向无环图 .

（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.
algorithm recursion dynamic-programming

1 回答

  • 0

    设 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 .

    回复于

相关问题