原文链接：http://www.mydrs.org/program/list.asp?id=250
[例] 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。
解题过程如下：
顶点图
矩阵图
下面，给出[例]的程序题解。
Program Short(input,output);
Const Max=100;
Var
N,St,En, { 顶点数，起点，终点 }
I,J,X : Integer;
way : Array[1..Max,1..Max] of Integer; { 线路网络的带权矩阵 }
NetDot : Array[1..Max] of Record
{NetDot[j].Ne--从J点出发的决策}
{NetDot[j].CostSt--从J点至En点的最短距离}
Ne,Cost:Integer
End;
F : Text; { 文件变量 }
Str : String; { 文件名串 }
Begin
Write('File name=',Str); { 读入文件名串 }
Readln(Str);
Assign(F,Str); { 文件名与文件变量连接 }
Reset(F); { 读文件准备 }
Readln(F,N,St,En); { 读入顶点数，起点，终点 }
(*writeln('N=',N:4,'St=',St:4,'En=',En:4);*)
For I:= 1 to N Do { 读入各点间连线的距离 }
For J:= 1 to N Do Read(F,Way[I,J]);
Close(F);
For I:= 1 to N Do NetDot[I].Cost:=Maxint; { St至各点的最短路线长度初始化 }
NetDot[En].Cost:=0; NetDot[En].Ne :=0; { 从最后一段开始，由后何前逐步递推 }
{ 以下两句倒推的求解。 }
For J:= N Downto 1 Do
For X:= N Downto J Do
If ( Way[J,X] >0 ) And ( NetDot[X].Cost <> Maxint )
And(Way[J,X]+NetDot[X].Cost<NetDot[J].Cost ) Then
{ 若En至x点的最短路己经求出，且加入边(j，x)后使得En至j的路线目前最短 }
Begin
NetDot[J].Cost:=NetDot[X].Cost+Way[J,X] ;
{ 则记下最短路线长度 }
NetDot[J].Ne:=X;{ jX}
End;
If NetDot[St].Cost=Maxint Then
Writeln('NoWay')
Else
Begin { 否则从起点出发，按计算顺序反推最短路线 }
X:=St;
While X<>0 Do Begin
Write(X:3,' ');
X:=NetDot[X].Ne;
End;
End;
(*read(Str);*)
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
作者：
来源：淮安教学科研网
时间：2001-10-14
上一篇：动态规划问题的程序框图
下一篇：SGOI5《彩虹7号》解题报告