城市交通費用PASCAL程序解.docVIP

動態(tài)規(guī)劃問題的PASCAL程序解例 下圖表示城市之間的交通路網，線段上的數字表示費用，單向通行由A-E。試用動態(tài)規(guī)劃的最優(yōu)化原理求出A-E的最省費用。解題過程如下：頂點圖矩陣圖下面，給出例的程序題解。Program Short(input,output);Const Max=100;VarN,St,En, 頂點數，起點，終點 I,J,X : Integer;way : Array1.Max,1.Max of Integer; 線路網絡的帶權矩陣 NetDot : Array1.Max of RecordNetDotj.Ne-從J點出發(fā)的決策NetDotj.CostSt-從J點至En點的最短距離Ne,Cost:IntegerEnd;F : Text; 文件變量 Str : String; 文件名串 BeginWrite(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,WayI,J);Close(F);For I:= 1 to N Do NetDotI.Cost:=Maxint; St至各點的最短路線長度初始化 NetDotEn.Cost:=0; NetDotEn.Ne :=0; 從最后一段開始，由后何前逐步遞推 以下兩句倒推的求解。 For J:= N Downto 1 DoFor X:= N Downto J DoIf ( WayJ,X 0 ) And ( NetDotX.Cost Maxint )And(WayJ,X+NetDotX.CostNetDotJ.Cost ) Then 若En至x點的最短路己經求出，且加入邊(j，x)后使得En至j的路線目前最短 BeginNetDotJ.Cost:=NetDotX.Cost+WayJ,X ; 則記下最短路線長度 NetDotJ.Ne:=X; jXEnd;If NetDotSt.Cost=Maxint ThenWriteln(NoWay)ElseBegin 否則從起點出發(fā)，按計算順序反推最短路線 X:=St;While X0 Do BeginWrite(X:3, );X:=NetDotX.Ne;End;End;(*read(Str);*)End.輸入文件名為Q01.TXT其內容如下：10 1 100 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 -