臺灣博碩士論文加值系統

本論文主要研究在網路模型中,尋求最短路徑(Shortest Path)和最大流量(Maximum Flow)等問題之最佳演算法.在求最短路徑問題上,古典的Dijkstra演算法頗受歡迎.但在儲存空間與計算效率(時間)上,仍有很大改善的空間.而近年來,一種運用矩陣運算和最小生成樹的概念已被Juang所提出.然而更進一步的設計程式執行實作(Implementations),適用性,與驗證,仍未被探究.本文因此詳加探討且提出一個修正的新演算法,它結合Prim的求最小生成樹演算法之概念與Juang的矩陣運算方法,所設計出的新方法.至於求最大流量問題,依據最大流最小切定理(Max-Flow Min-Cut Theorem),可求圖的最小切集之所有邊的流量總和,即是該圖的最大流量.而求最小切集也可用矩陣運算法得之,因此一同在本論文提出.我們對這兩個問題的相關的演算法均應用MATLAB軟體來設計程式執行實作.實驗測試的結果也一併展示.這些結果驗證了本文所提出的演算法是一個正確實用,有效率,且有競爭力的方法.

In this thesis, we investigate the problems of the shortest path and the maximum flow in network models. Regarding finding the shortest path,the classical algorithm of Dijkstra is good and popular. However, it still can be improved in the storage space and the efficiency of computation.Recently, a new approach of solving this problem, by applying matrix operations and finding the minimum spanning tree, was proposed by Juang. But, the further work, such as the implementation, adaptiveness, and verification, has not been explored yet.We therefore present a modified method by combining the concept of Prim's algorithm and Juang's matrix-operation scheme, and also design a new algorithm for finding the shortest path.

As the problem of solving the maximum flow, it can be transformed, based on the theorem of Max-Flow Min-Cut, into the problem of finding the total flow of the minimum cut set. Since it can also be obtained by the method of matrix operations,we therefore present it in this thesis as well. All algorithms related to both problems are implemented by {\sc Matlab} software. The experimental results are also demonstrated. They are good evidences to verify that our approaches are correct, efficient, and applicable.

1 簡介與背景. . . . . . . . . . . . . . . . . . . . . . . . .2
1.1 簡介. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 背景與源由. . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 最短路徑問題. . . . . . . . . . . . . . . . . . . . . 3
1.1.3 最大流量問題. . . . . . . . . . . . . . . . . . . . . 4
1.2 名詞符號與基礎理論. . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 名詞定義與符號. . . . . . . . . . . . . . . . . . . . 5
1.2.2 基礎理論. . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 最短路徑的傳統解法. . . . . . . . . . . . . . . . . . . . . . 10
1.4 本文結構. . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 最小生成樹和最大流量演算法14
2.1 最小生成樹. . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Kruskal演算法. . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Prim演算法. . . . . . . . . . . . . . . . . . . . . . 16
2.2 Juang的最小生成樹演算法. . . . . . . . . . . . . . . . . . . 17
2.3 最小切集/最大流量. . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 Ford-Fulkerson’s algorithm . . . . . . . . . . . . . . 22

2.3.2 Juang的最小切演算法. . . . . . . . . . . . . . . . . 25
3 最短路徑演算法及改良方法30
3.1 Juang的最短路徑演算法. . . . . . . . . . . . . . . . . . . . 30
3.2 JSP演算法分析. . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 JMST 與JSP 演算法之缺陷. . . . . . . . . . . . . . . . . 39
3.4 新修正之應用矩陣運算法. . . . . . . . . . . . . . . . . . . . 42
3.4.1 MOA-MST 演算法. . . . . . . . . . . . . . . . . . 42
3.4.2 MOA-SP 演算法. . . . . . . . . . . . . . . . . . . . 47
4 測試比較與結論55
4.1 MOA-SP演算法. . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Juang 的最小切演算法與Ford-Fulkerson 演算法之測試比較. 67
4.3 結論. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
.1 JMC.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
.2 Ford-Fulkerson.m(Part 1) . . . . . . . . . . . . . . . . . . 75
.3 Ford-Fulkerson.m(Part 2) . . . . . . . . . . . . . . . . . . 76
.4 Ford-Fulkerson.m(Part 3) . . . . . . . . . . . . . . . . . . 77
.5 JSP.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
.6 MOA-SP.m(Part 1) . . . . . . . . . . . . . . . . . . . . . . 79
.7 MOA-SP.m(Part 2) . . . . . . . . . . . . . . . . . . . . . . 80
.8 MOA-SP.m(Part 3) . . . . . . . . . . . . . . . . . . . . . . 81

[1] E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numeriche Mathematik 1, pp.269-271, 1959.
[2] G. Gallo and S. Pallottino, “Shortest Paths Algorithms,” Annals of Operations Research 13, 3-79, 1988.
[3] F. Benjamin Zhan, “Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures,” Journal of Geographic Information and Decision Analysis, vol.1, no.1, pp. 69-82, 1997.
[4] J. Y. Juang, “ Numerical Method to the Solution of Optimization Problems in Network Model Analysis,” Proc. 2008 CACS Automatic Control Conference, ” 2008-IACC, National Cheng Kung University, Tainan, Taiwan, 2008.
[5] J. B. Kruskal, Jr, “ On The Shortest Spanning Subtree of A Graph
and The Traveling Salesman Problem, ”Proceedings of the American Mathematical Society Vol. 7, No. 1, pp. 48-50, 1956
[6] F. B. Zhan and C. E. Noon, “Shortest Path Algorithms: An Evaluation Using Real Road　Networks,” Transportation Science, Vol. 32, No. 1, pp. 65-73, 1998.
[7] R. C. Prim, “Shortest Connection Networks And Some Generalizations,”BSTJ 36: 6. November, 1957.
[8] M. Sollin, “Le trace de canalisation". Programming, Games, and Transportation Networks,” 1965 (in French).
[9] R. B. Dial, “Algorithm 360: Shortest Path Forest with Topological Ordering,” Communications of the ACM, 12, pp. 632-633, 1969.
[10] M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithm,” 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. 1984.
[11] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin,“ Network Flows: Theory, Algorithms and Applications,” Englewood Cliffs, NJ: Prentice Hall, 1993.
[12] B. V. Cherkassky, A. V. Goldberg, and T. Radzik, “Shortest Paths Algorithms: Theory and Experimental Evaluation,” Technical Report, Computer Science Department, Stanford University, 93-1480, 1993.
[13] L. R. Ford and D. R. Fulkerson, “ Flow in Network,” Princeton, N. J. : Princeton University Press, 1962.
[14] W.　L. Winston, “Operations Research: Applications and Algorithms,” 3rd ed. Duxbury Press, CA, 394-459, 1994.
[15] G. Chartrand and O.R. Oellermann, “Applied and Algorithmic Graph Theory,” McGraw-Hill, 1993.
[16] T. H. Corman, C. E. Leiserson, R. L. Rivest, and C. Stein, “ Introduction to Algorithms,” McGraw-Hill, 2001.