GPS寻找最优路径

来自计算思维百科
跳转至: 导航搜索

假设图1中无向图G,顶点表示城市,边上权值表示两个城市之间的距离或时间开销。图中任两个顶点之间有多条路径,最短路径是指在两个顶点的所有路径中求边权值之和最小的路径。

以图中顶点0到顶点6的最短路径为例进行求解。

                RTENOTITLE

                       图1动态规划求解最短路径例子

显然,从0顶点到6顶点的最短路径,若经过k顶点,则最短路径中从0到k的路径也是0到k的最短路径。这一点用反证法可以证明,这里略去。

用动态规划求解最短路径基于上述原理,为计算从顶点0到顶点6的最短路径,只需依次求得从顶点0到各中间顶点的最短路径。按照与0顶点的距离,将整个求解过程划分为5个阶段。

定义cost[i] :从顶点0到顶点i的最短路径,path[i]记录从0到i的最短路径上顶点i的前一顶点。初始,cost[0] = 0。后续各阶段,依次递推计算即可。

第0阶段:cost[0] = 0

第1阶段:cost[1] = cost[0]+4 = 4,path[1] = 0

     cost[2] = cost[0]+5 = 5,path[2] = 0

第2阶段:cost[3] = min{cost[0]+8,cost[1]+4,cost[2]+5} = 8,path[3] = 0

第3阶段:cost[4] = min{cost[3]+8,cost[1]+6} = 10,path[4] = 1

     cost[5] = min{cost[3]+9,cost[2]+7} = 12,path[5] = 2

第4阶段:cost[6] = min{cost[4]+5,cost[3]+9,cost[5]+4} = 15,path[6] = 4

根据计算得,从顶点0到顶点6的最短路径值为15。从path[6]向前回溯,得到最短路径为:0->1->4->6。