最短路径动态规划问题及C语言实现探讨

王学军

摘要：动态规划算法是一种研究多阶段决策问题的算法.用动态规划方法求最短路问题，要求所求问题具有明显的阶段。该文以动态规划理论为指导，研究了动态规划算法求解最短路径的基本原理及步骤，编写了基于动态规划算法的C语言程序，辅助完成最短路径的求解。

关键词：最短路径；动态规划；C 语言编程

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）09-2191-03

1 概述

数学源于生活，又服务于生活.它是一门研究现实世界中的数量关系与空间形式的学科.当今社会，随着物质水平的不断提高，生活需求的不断扩大，自然资源的不断开发利用.像天然气管道铺设问题，厂区布局问题，旅行费用最小问题等都已成为我们平时经济生活中的普遍问题.它们其实都可以化归为最短路线问题，而最短路问题实质上是一个组合优化问题[1]。

动态规划方法主要是研究与解决多阶段决策过程的最优化问题，它将求解分成多阶段进行，不但求出了全过程的解，还能求出后部子过程的一组解，在求解一些生活实际问题时，更显其优越性。为了快速、简单的计算最短路径，节约运输时间与成本，该文利用动态规划的思想编写了C语言程序，解决物流运输过程中多地点的最短路径的选择问题。

2 最短路径问题

2.1 最短路径问题算法的基本思想

在求解网络图上节点间最短路径的方法中，目前国内外一致公认的较好算法有迪杰斯特拉（Dijkstra）及弗罗伊德（Floyd）算法。这两种算法中，网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，直到获得最后的优化路径[2]。

Dijkstra算法是图论中确定最短路的基本方法，也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径，通常采用两种方法。一种方法是每次以一个结点为源点，重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法，其时间复杂度为[On3]，虽然与重复执行Dijkstra算法n次的时间复杂度相同，但其形式上略为简单，且实际运算效果要好于前者。

2.2 最短路径问题算法的基本步骤[3]

这样经过有限次迭代则可以求出[v1]到[vn]的最短路线。

（2）Floyd算法的基本步骤

（3）动态规划算法基本步骤

我们将具有明显的阶段划分和状态转移方程的规划称为动态规划[1]。在解决多个阶段决策问题时采用动态规划法是一个很有效的措施，同时易于实现。

根据动态规划的基本概念，可以得到动态规划的基本步骤：1）确定问题的决策对象。2）对决策过程划分阶段。3）对各阶段确定状态变量。4）根据状态变量确定费用函数和目标函数。5）建立各阶段状态变量的转移过程，确定状态转移方程。

根据动态规划的基本模型，确定用动态规划方法解题的基本思路，是将一个[n]阶段决策问题转化为一次求解[n]个具有递推关系的单阶段的决策问题，以此来简化计算过程.其一般步骤如下：

用于衡量所选决策优劣的函数称为指标函数.指标函数有有阶段的指标函数和过程的指标函数之分.阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的某种效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]来表示某一阶段的决策的最短路径。过程的指标函数是指从状态[xn（k=1，2，...，n）]出发至过程最终，当采取某种子策略时，按预定的标准得到的效益值。这个值既与[xk]本身的状态值有关，又与[xk]以后所选取的策略有关，它是两者的函数值，记作[dk，nxk，uk，xk+1，uk+1，…xn，un]。过程的指标函数又是它所包含的各阶段指标函数的函数。本文研究的过程的的指标函数是其各阶段指标函数的和的形式.当[xk]的值确定后，指标函数的值就只同k阶段起的子策略有关。对应于从状态[xk]出发的最优子策略的效益值记作[fkxk]，于是在最短路问题中，有[fkxk=mindk，n]。动态规划求解最短路径程序流程图如图2所示。

3 最短路径态规划实际应用举例

设某物流配送网络图由12个配送点组成，点1为配送中心起点，12为终点，试求自终点到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离[4]。

首先用动态规划法来讨论图3的最短路径，由图可知：

1）集合[ξ4]中有点9、10、11，它们在一步之内可到达点12；

2）集合[ξ3]中有点6，7，8，它们不超过两步就可达到点12；

3）集合[ξ2]中包括点 2、3、4、5，不超过三步就可到达点12；

4）集合[ξ1]中包括点1，不超过四步可到达点12；

按照动态规划法类推，得到最优路径长为16，径路通过点为1，2，7，10，12和1，3，6，10，12。

根据动态规划算法编写C语言计算程序[5] [6]，计算得到实验结果如下图4所示：

由图4可以看出程序得到的结果与本文推出的结果一样。证明了本文编写的C语言程序是正确的。

4 结束语

综上所述，用动态规划解决多阶段决策问题效率高，而且思路清晰简便，同时易于实现.我们可以看到，动态规划方法的应用很广泛，已成功解决了许多实际问题，具有一定的实用性。此种算法我们用动态规划思想来编程，并解决相应的问题，其在 VC 环境下实现，能方便快速的计算出到达目的地的最短距离及路径，节省更多的运输时间与成本。不过，该文只考虑了动态规划算法在生活中的简单运用，在实际生活中可能存在多个目的地或者更复杂的情况.因此我们可以考虑将其进行改进或者结合启发式算法，使之更好的运用在实际生活中，这有待于以后的继续研究。

参考文献：

[1] 杜彦娟.利用动态规划数学模型求解最短路径[J].煤炭技术，2005（1）：94-95.

[2] 蒋琦玮，陈治亚.物流配送最短径路的动态规划方法研究[J].系统工程，2007（25）：27-29.

[3] 朱建民.运筹学——典型例题与解法[EB/OL].http：//www.zytxs.com/，2003.