基于JAVA的最短路徑算法分析與實(shí)現(xiàn)

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