原文链接：http://www.mydrs.org/program/list.asp?id=341
[例] 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。
解题过程如下：
顶点图
矩阵图
下面，给出[例]的程序题解。
CONST Max99 = 99
CONST Max99Int = 9999
DIM N, St, En AS INTEGER ' 顶点数，起点，终点
DIM I, J, X AS INTEGER
DIM Way(Max99, Max99) AS INTEGER ' 线路网络的带权矩阵
TYPE Card
Ne AS INTEGER
Cost AS INTEGER
END TYPE
DIM NetDot(Max99) AS Card
' NetDot(J).Ne--从J点出发的决策
' NetDot(J).Cost--从起点J点出发En的最短路线长度
DIM Str AS STRING ' 文件名串
INPUT "File name=", Str ' 读入文件名串
OPEN Str FOR INPUT AS #1
INPUT #1, N, St, En ' 读入顶点数，起点，终点
FOR I = 1 TO N ' 读入各点间连线的距离
FOR J = 1 TO N
INPUT #1, Way(I, J)
NEXT J
NEXT I
CLOSE (1)
FOR I = 1 TO N
NetDot(I).Cost = Max99Int ' St至各点的最短路线长度初始化
NEXT I
NetDot(En).Cost = 0
NetDot(En).Ne = 0 ' 从最后一段开始，由后何前逐步递推
' 以下两句倒推的求解。
FOR J = N TO 1 STEP -1
FOR X = N TO J STEP -1
IF Way(J, X) > 0 AND NetDot(X).Cost <> Max99Int AND Way(J, X) + NetDot(X).Cost < NetDot(J).Cost THEN
' 若En至x点的最短路己经求出，且加入边(j，x)后使得En至j的路线目前最短
NetDot(J).Cost = NetDot(X).Cost + Way(J, X)
' 则记下最短路线长度
NetDot(J).Ne = X
END IF
NEXT X
NEXT J
IF NetDot(St).Cost = Max99Int THEN
PRINT "NoWay"
ELSE
' 否则从起点出发，按计算顺序反推最短路线
X = St
WHILE X <> 0
PRINT X, " ";
X = NetDot(X).Ne
WEND
END IF
END
输入文件名为Q01.TXT其内容如下：
10 1 10
0 2 5 1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 12 14 -1 -1 -1 -1
-1 -1 0 -1 6 10 4 -1 -1 -1
-1 -1 -1 0 -1 12 11 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 3 9 -1
-1 -1 -1 -1 -1 0 -1 6 5 -1
-1 -1 -1 -1 -1 -1 0 -1 10 -1
-1 -1 -1 -1 -1 -1 -1 0 -1 5
-1 -1 -1 -1 -1 -1 -1 -1 0 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 0
运行结果如下：
File Name=q01.txt
1 3 5 8 10
作者：
来源：淮安信息技术教研网
时间：2002-03-23
上一篇：动态规划问题的经典实例
下一篇：第八次曙光信息学奥赛公告