基于JAVA的最短路徑算法分析與實現

　　 摘要：最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。本文采用JAVA語言來實現路徑算法中的Johnson算法。
　　 關鍵詞：最短路徑 Java Johnson算法 算法實現
　　
　　 最短路徑問題是圖論研究中的一個經典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括：確定起點的最短路徑問題。即已知起始結點，求最短路徑的問題；確定終點的最短路徑問題。與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題；確定起點終點的最短路徑問題。即已知起點和終點，求兩結點之間的最短路徑；全局最短路徑問題——求圖中所有的最短路徑。
　　 一、最短路徑算法的實現策略
　　 用于解決最短路徑問題的算法被稱作“最短路徑算法”，有時被簡稱作“路徑算法”。最常用的路徑算法有：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
　　 所謂單源最短路徑問題是指：已知圖G＝（V，E），我們希望找出從某給定的源結點S∈V到V中的每個結點的最短路徑。
　　 首先，我們可以發現有這樣一個事實：如果P是G中從vs到vj的最短路，vi是P中的一個點，那么，從vs沿P到vi的路是從vs到vi的最短路。
　　 筆者以3Dijkstra算法為例，Dijkstra算法是典型最短路算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優解，但由于它計算的節點很多，所以效率低下。Dijkstra算法的輸入包含了一個有權重的有向圖G，以及G中的一個來源頂點S。我們以V表示G中所有頂點的集合，以E表示G中所有邊的集合