臺灣博碩士論文加值系統

從網路模型的角度來看，最短路徑的解法就是在特定的網路中尋找一條連接兩個節點的路徑，透過Floyd-Warshall演算法基本運算可以得到各個節點之間的最短路徑。本研究主要是以最短路徑演算法為基礎，有效率的的求解禁止路徑問題。在無向網路圖中以Floyd-Warshall演算法得到一個點對點所組成的最短路徑矩陣，進而推導至在同一個網路圖中，某些節點與節點之間所連接的edge被禁止時，不需要再以Floyd-Warshall演算法重新計算，而能夠從矩陣當中的數值直接做運算，進而簡化運算步驟。

The essence of this paper is to establish a model for solving the forbidden paths problem. The basic idea of this research is to use the Floyd-Warshall algorithm to calculate the shortest distance between any pair of nodes and modify the solution in case that some edges are removed. The exactness and uniqueness are proved in this paper. This model often an efficient way to solve the forbidden paths problem.

中文摘要 -------------------------------------------------------------------------- i
英文摘要 -------------------------------------------------------------------------- ii

誌謝 -------------------------------------------------------------------------- iii
目錄 -------------------------------------------------------------------------- iv
表目錄 -------------------------------------------------------------------------- vi
圖目錄 -------------------------------------------------------------------------- vii
第一章 緒論-------------------------------------------------------------------- 1
1.1 研究背景與動機----------------------------------------------------- 1
1.2 研究目的-------------------------------------------------------------- 2
1.3 研究流程-------------------------------------------------------------- 2
1.4 研究架構-------------------------------------------------------------- 3
第二章 文獻探討-------------------------------------------------------------- 4
2.1 最短路徑問題------ -------------------------------------------------- 4
2.1.1 標記設定法----------------------------------------------------------- 5
2.1.2 標記修正法----------------------------------------------------------- 5
2.1.3 Floyd-Warshall 演算法---------------------------------------------- 6
2.2 K條最短路徑問題--------------------------------------------------- 7
2.3 禁止路徑問題-------------------------------------------------------- 9
2.3.1 Martins演算法-------------------------------------------------------- 10
2.3.2 決定性有限狀態機--------------------------------------------------- 10
2.3.3 SPPFP演算法--------------------------------------------------------- 11
第三章 研究方法-------------------------------------------------------------- 12
3.1 最短路徑概述-------------------------------------------------------- 12
3.1.1 單點最短路徑-------------------------------------------------------- 12
3.1.2 任一節點間的最短路徑--------------------------------------------- 12
3.2 Floyd-Warshall演算法----------------------------------------------- 13
3.2.1 Floyd-Warshall基本介紹-------------------------------------------- 13
3.2.2 Floyd-Warshall演算法步驟----------------------------------------- 14
3.3 簡化Floyd-Warshall演算法後禁止路徑的運算----------------- 17
3.3.1 問題定義-------------------------------------------------------------- 17
3.3.2 求解演算法----------------------------------------------------------- 17
3.4 演算法的合理性----------------------------------------------------- 19
3.5 範例介紹-------------------------------------------------------------- 20
第四章 討論-------------------------------------------------------------------- 24
4.1 10x10無向性網路圖------------------------------------------------- 24
4.2 15x15無向性網路圖------------------------------------------------- 27
4.3 20x20無向性網路圖------------------------------------------------- 32
第五章 結論與未來研究方向------------------------------------------------ 36
5.1. 結論-------------------------------------------------------------------- 36
5.2. 未來研究方向-------------------------------------------------------- 36
參考文獻 -------------------------------------------------------------------------- 38
附錄一 -------------------------------------------------------------------------- 40
附錄二 -------------------------------------------------------------------------- 43
附錄三 -------------------------------------------------------------------------- 48

1.丁華淵(2007)，考慮禁止路徑的最短路徑演算法，國立臺灣科技大學，碩士論文。
2.林蔚明(2004)，路口延滯下路徑演算法之研究，逢甲大學，碩士論文。
3.陳芸伯(2004)，考慮貨物擺設及行經特定點之收送貨途程問題，國立東華大學，碩士論文。
4.張進益(2007)，建築動線最短路徑模擬之研究，逢甲大學，碩士論文。
5.蕭惠如(2003)，緊急事故下物件導向決策支援系統之建立，逢甲大學,碩士論文。
6.Ahuja, R. K., Magnanti, T. L. & Orlin, J. B. (1993), Network Flows：Theory , Algorithms , and Applications, Prentice-Hall Inc.
7.Chen, Y. L., and Yang, H. H. (2000), “Shortest paths in traffic-light networks,” Transportation Research Part B 34, pp.241-253.
8.Chen, Y. L. & Yang, H. H. (2005) “Finding K shortest looping paths in a traffic-light network”, Computers & Operations Research, 32, pp.571–581.
9.Chen, Y. L. & Yang, H. H. (2006) “Finding K shortest looping paths with waiting time in a time–window network’ Applied Mathematical Modeling, 30, pp.458–465.
10.Dion, F., Rakha, H. & Kang, Y. S. (2004) “Comparison of delay estimates at under-saturated and over-saturated pre-timed signalized intersections,” Transportation Research Part B, 38, pp.99-122.
11.Hoffman, W. & Pavley, R. (1959) “A method for the solution of the N’th best path problem”, Journal of the Association for Computing Machinery, 6, pp.506-5014.
12.Jimenez, V. M. & Marzal, A. (1999) “Computing the k shortest paths a new algorithm and an experimental comparison”, Lecture notes in computer Science, 1688, pp.15-29.
13.Katoh, N., Ibaraki, T. & Mine H. (1982) “An efficient algorithm for k shortest simple paths”, Networks, 12, pp.411-427.
14.Kohl, N. & Madsen O.B.G. (1997) “ An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation”, Operations Research, 45, pp.395–406.
15.Martins, E. Q. V. (1984) “An algorithm for ranking paths that may contain cycles”, European Journal of Operational Research, 18, pp.123-130.
16.Shier, D. R. (1979) “On Algorithm for Finding the K Shortest Paths in a Network”, Network, 9, pp.195-214.
17.Suna, B., Henning, B., Markus, H. & Martin, K. (2009) “On input-revolving deterministic and nondeterministic finite automata”, Information and Computation, pp.1-16.
18.Villeneuve, D. & Desaulniers, G. (2005) “The shortest path problem with forbidden paths”, European Journal of Operational Research, 165, pp.97-107.
19.Yen, Y. J. (1971) “Finding the k shortest loopless paths in a network”, Management Science, 17(11), pp.712-716.
20.Zijpp, N. J. & Catalano, S. F. (2005) “Path enumeration by finding the constrained k-shortest paths”, Transport Research B, 39, pp.545-563.