[例] 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由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