动态规划-最短路径问题.docx

最短路径问题下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。求城市who与城市E的最短距离找到目标城市初始化最短路径为最大S未访问置访问标志累加城市E至城市Who的路径长度回溯后，恢复城市i未访问状态如果最短则记下返回最短路径长度计算最短路径长度j；现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设DiSx为城市x到城市E的最短路径长度(x表示任意一个城市)；mapi,j表示i,j两个城市间的距离，若mapi，j=0,则两个城市不通；我们可以使用回溯法来计算DiSx：varS：未访问的城市集合；functionsearch(whox)：integer；beginifWho=EThenSearch0Elsebeginminmaxint；fori取遍所有城市Doif(mapWho，i0有路)and(ithenbeginS-S