本文代码点击这里下载。
动态规划方法
如果节点位于
到
的最短路径上,那么
到
的路径也必须是
和
之间的最短路径。这种“分而治之”(devide-and-conquer)的思想,被称为动态规划(dynamic programming)。
异步动态规划方法(ASYNCHDP)
记节点到目标节点
的最短路径为
。从
到
的经过
(是
的邻居)的最短路径可通过
给出,并且
. 基于这种思想,给出ASYNCHDP方法的伪代码如下。
ASYNCDP算法伪代码
一个ASYNCDP算法的例子:
ASYNCDP算法寻找最短路径的例子










网友评论