最短路徑動態規劃問題及其程序設計

［摘要］論文以最短路徑問題為例，在給出佛洛伊德算法的基礎上，設計了求解該算法的計算程序，這樣可大大提高最短路徑計算的效率。

［關鍵字］最短路徑，動態規劃，程序設計

1佛洛伊德算法

2.動態規劃求解的佛洛伊德算法程序設計

如下圖所示：給定一個線路網絡，兩點之間連線上的數字表示兩點間的距離，求一條從A到E的路線，使總距離為最短。

為了減少上述問題的計算工作量，我們編制求解動態規劃算法的VBA程序如下：

Sub js()

Dim n， i， j， k As Integer

n = 9

Dim d(9， 9)， p(9， 9)， path(9)， distance As Integer

Rem 將數據存于數組d(i，j)中

For i = 1 To n

For j = 1 To n

d(i， j) = Cells(i， j)

Next j

Next i

For i = 1 To n

For j = i + 1 To n

If d(i， j) < 99999 Then

d(j， i) = d(i， j)

End If

Next j

Next i

Rem 定義距離矩陣

For i = 1 To n

For j = 1 To n

p(i， j) = 0

Next j

Next i

For i = 1 To n

For j = 1 To n

If i = j Then

p(i， j) = 99999

Else

p(i， j) = i

End If

Next j

Next i

Rem 計算距離和路徑

For k = 1 To n

For i = 1 To n

For j = 1 To n

If i <> j Then

If d(i， k) + d(k， j) < d(i， j) Then

d(i， j) = d(i， k) + d(k， j)

p(i， j) = k

End If

End If

Next j

Next i

Next k

Rem 輸出距離和路徑

distance = d(1， n)

For i = 1 To n

path(i) = 0

Next i

Count = 9

i = 1

While Count > 1

path(i) = p(1， Count)

i = i + 1

Count = p(1， Count)

Wend

Cells(20， 1) = distance

For i = 1 To n

Cells(21， i) = path(i)

Next i

End Sub

主要參考文獻

[1]朱順泉.管理科學研究方法[M].北京：清華大學出版社，2007

[2]運籌學編寫組.運籌學[M].清華大學出版社，1992

[3]丁以中等.管理科學[M].清華大學出版社，2003

[4]楊世勝.計算機在企業管理中應用[M].上海交通大學出版社，1985

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”