Asynchronous dynamic programming (ASYNCHDP) 算法求最短路径

本文代码请进入原文下载。

动态规划方法

如果节点$x$位于$s$到$t$的最短路径上，那么$x$到$t$的路径也必须是$x$和$t$之间的最短路径。这种“分而治之”（devide-and-conquer）的思想，被称为动态规划（dynamic programming）。

异步动态规划方法（ASYNCHDP）

记节点$i$到目标节点$t$的最短路径为$h^(i)$。从$i$到$t$的经过$j$（是$i$的邻居）的最短路径可通过$f^ (i,j)=w(i,j)+h^(j)$给出，并且$h^(i)=min_j f^*(i,j)$. 基于这种思想，给出ASYNCHDP方法的伪代码如下。

一个ASYNCDP算法的例子：