無向圖的最短路徑算法JAVA實作

一，問題描述

給出一個無向圖，指定無向圖中某個頂點作為源點。求出圖中所有頂點到源點的最短路徑。

無向圖的最短路徑其實是源點到該頂點的最少邊的數目。

本文假設圖的資訊儲存在檔案中，通過讀取檔案來構造圖。檔案内容的格式參考這篇文章第一部分。

二，算法實作思路

無向圖的最短路徑實作相對于帶權的有向圖最短路徑實作要簡單得多。

源點的最短路徑距離為0，從源點開始，采用廣度優先的順序，首先将與源點鄰接的頂點的路徑求出，然後再依次求解圖中其他頂點的最短路徑。

由于頂點的最短路徑的求解順序是一個廣度優先的順序，是以需要一個輔助隊列。初始時，将源點的最短路徑距離設定為0，将源點入隊列。

然後，在一個while循環中，從隊列中彈出頂點，周遊該頂點的鄰接點，若該鄰接點的距離未被更新過（表示該鄰接點未被通路過），更新鄰接點的最短路徑距離為該頂點的距離加上1，并将所有的鄰接點入隊列。

三，最短路徑算法的實作

感覺該算法的實作與二叉樹的層序周遊，有向圖的拓撲排序算法實作都非常的相似。他們都采用了廣度的思想在裡面。

廣度優先的思想就是：處理完某個頂點後，去處理該頂點的所有鄰接點，處理完它的鄰接點後，再去處理更遠（更外層）的頂點。

算法的代碼如下：

1     /*
 2      * 計算源點s到無向圖中各個頂點的最短路徑
 3      * 需要一個隊列來儲存圖中的頂點,初始時,源點入隊列,然後以廣度的形式向外擴散求解其他頂點的最短路徑
 4      */
 5     private void unweightedShortestPath(Vertex s){
 6         //初始化
 7         Queue<Vertex> queue = new LinkedList<>();
 8         s.dist = 0;
 9         queue.offer(s);//将源點dist設定為0并入隊列
10         
11         while(!queue.isEmpty()){
12             Vertex v = queue.poll();
13             for (Edge e : v.adjEdges) {//掃描v的鄰接邊(點)
14                 if(e.endVertex.dist == Integer.MAX_VALUE){//如果這個頂點(e.endVertex)未被通路(每個頂點隻會入隊列一次)
15                     e.endVertex.dist = v.dist + 1;//更新該頂點到源點的距離
16                     queue.offer(e.endVertex);
17                     e.endVertex.preNode = v;//設定該頂點的前驅頂點
18                 }//end if
19             }//end for
20         }//end while
21     }

第11行while循環，每個頂點出隊列一次，第13行for循環，表示每條邊被處理一次，故算法的時間複雜度為O（V+E）

第14行if語句表明，圖中每個頂點隻會入隊列一次。因為，頂點入隊列後，該頂點的 dist 設定為 v.dist+1，不再是 Integer.MAX_VALUE

四，完整代碼實作

NonDirectedGraph.java構造圖并實作最短路徑算法

1 import java.util.Collection;
  2 import java.util.LinkedHashMap;
  3 import java.util.LinkedList;
  4 import java.util.List;
  5 import java.util.Map;
  6 import java.util.Queue;
  7 
  8 /*
  9  * 求解無向圖的單源最短路徑
 10  */
 11 public class NonDirectedGraph {
 12     private class Vertex{
 13         private String vertexLabel;//頂點辨別
 14         private List<Edge> adjEdges;//與該頂點鄰接的邊(點)
 15         private int dist;//頂點距離(該頂點到起始頂點的距離)
 16         private Vertex preNode;
 17         
 18         public Vertex(String vertexLabel) {
 19             this.vertexLabel = vertexLabel;
 20             adjEdges = new LinkedList<>();
 21             dist = Integer.MAX_VALUE;
 22             preNode = null;
 23         }
 24     }
 25     private class Edge{
 26         private Vertex endVertex;
 27         public Edge(Vertex endVertex) {
 28             this.endVertex = endVertex;
 29         }
 30     }
 31     
 32     private Map<String, Vertex> nonDirectedGraph;//儲存了圖中所有的頂點，邊的關系以List形式儲存在Vertex類中
 33     private Vertex startVertex;//圖的起始頂點
 34     
 35     public NonDirectedGraph(String graphContent) {
 36         nonDirectedGraph = new LinkedHashMap<>();
 37         buildGraph(graphContent);
 38     }
 39     
 40     private void buildGraph(String graphContent){
 41         String[] lines = graphContent.split("\n");
 42         
 43         String startNodeLabel, endNodeLabel;
 44         Vertex startNode, endNode;
 45         for(int i = 0; i < lines.length; i++){
 46             String[] nodesInfo = lines[i].split(",");
 47             startNodeLabel = nodesInfo[1];
 48             endNodeLabel = nodesInfo[2];
 49             
 50             endNode = nonDirectedGraph.get(endNodeLabel);
 51             if(endNode == null){
 52                 endNode = new Vertex(endNodeLabel);
 53                 nonDirectedGraph.put(endNodeLabel, endNode);
 54             }
 55             
 56             startNode = nonDirectedGraph.get(startNodeLabel);
 57             if(startNode == null){
 58                 startNode = new Vertex(startNodeLabel);
 59                 nonDirectedGraph.put(startNodeLabel, startNode);
 60             }
 61             Edge e = new Edge(endNode);
 62             //對于無向圖而言,起點和終點都要添加邊
 63             endNode.adjEdges.add(e);
 64             startNode.adjEdges.add(e);
 65         }
 66         startVertex = nonDirectedGraph.get(lines[0].split(",")[1]);//總是以檔案中第一行第二列的那個辨別頂點作為源點
 67     }
 68     
 69     public void unweightedShortestPath(){
 70         unweightedShortestPath(startVertex);
 71     }
 72     
 73     
 74     /*
 75      * 計算源點s到無向圖中各個頂點的最短路徑
 76      * 需要一個隊列來儲存圖中的頂點,初始時,源點入隊列,然後以廣度的形式向外擴散求解其他頂點的最短路徑
 77      */
 78     private void unweightedShortestPath(Vertex s){
 79         //初始化
 80         Queue<Vertex> queue = new LinkedList<>();
 81         s.dist = 0;
 82         queue.offer(s);//将源點dist設定為0并入隊列
 83         
 84         while(!queue.isEmpty()){
 85             Vertex v = queue.poll();
 86             for (Edge e : v.adjEdges) {//掃描v的鄰接邊(點)
 87                 if(e.endVertex.dist == Integer.MAX_VALUE){//如果這個頂點(e.endVertex)未被通路(每個頂點隻會入隊列一次)
 88                     e.endVertex.dist = v.dist + 1;//更新該頂點到源點的距離
 89                     queue.offer(e.endVertex);
 90                     e.endVertex.preNode = v;//設定該頂點的前驅頂點
 91                 }//end if
 92             }//end for
 93         }//end while
 94     }
 95     
 96     //列印圖中所有頂點到源點的距離及路徑
 97     public void showDistance(){
 98         Collection<Vertex> vertexs = nonDirectedGraph.values();
 99         for (Vertex vertex : vertexs) {
100             System.out.print(vertex.vertexLabel + "<--");
101             Vertex tmpPreNode = vertex.preNode;
102             while(tmpPreNode != null){
103                 System.out.print(tmpPreNode.vertexLabel + "<--");
104                 tmpPreNode = tmpPreNode.preNode;
105             }
106             System.out.println("distance=" + vertex.dist);
107         }
108     }
109 }

列印路徑也可以使用遞歸來實作：

1     public void showDistanceRecursive(Vertex v){
2         if(v.preNode != null){
3             showDistanceRecursive(v.preNode);
4         }
5         System.out.print(v.vertexLabel + "  ");
6     }

列印頂點 v 的路徑，第三行先列印 v 的前驅頂點的路徑，然後再在第5行列印 v 。

第5行的列印輸出語句在第三行的遞歸調用語句之後，故最裡層的遞歸調用最先被列印出來，最裡層的遞歸調用即源點，因為隻有源點的 preNode == null。

當所有的裡層遞歸調用傳回後，最終執行到最外層的遞歸調用處，執行第5行列印頂點 v 後，整個遞歸結束。

TestShortestPath.java是個測試類，用來測試結果。

1 public class TestShortestPath {//hapjin test
 2     public static void main(String[] args) {
 3         String graphFilePath;
 4         if(args.length == 0)
 5             graphFilePath = "F:\\xxx";
 6         else
 7             graphFilePath = args[0];
 8         
 9         String graphContent = FileUtil.read(graphFilePath, null);
10         NonDirectedGraph graph = new NonDirectedGraph(graphContent);
11         graph.unweightedShortestPath();
12         graph.showDistance();
13     }
14 }

FileUtil.java負責讀取存儲圖資訊的檔案。具體參考有向圖的拓撲排序算法JAVA實作

儲存圖的檔案内容如下：

0,0,1,4

1,0,2,7

2,0,3,3

3,1,2,3

4,1,4,2

5,3,4,3

6,2,5,2

7,4,5,2

測試輸出結果如下：

源點辨別是 0，

0 号頂點到 1 号頂點的最短距離為1，路徑為：0-->1

0 号頂點到 5 号頂點的最短距離為2，路徑為：0-->2-->5

.....

....

無向圖的最短路徑算法JAVA實作

繼續閱讀

程式設計－從矩陣左上角走到右下角

【NOIP 模拟題】郵差送信（最短路）

poj 2457 Part Acquisition最短路徑dijikstra迪傑斯特拉

CF E51 F. The Shortest Statement//lca(倍增)+dijkstra+dsu ※

最小生成樹->Prim算法和Kruskal算法

資料結構學習筆記——圖的應用（最短路徑和關鍵路徑）

三、最短路徑之Dijkstra算法

城市間緊急救援(Dijkstra算法)

迷宮最短路徑問題

bellman -ford算法的改進 spfa 算法

棋盤問題.…

有關無向圖的問題

2020年7月 pat 甲級第三題

最短路徑->Dijkstra算法和Floyd算法

200. 島嶼的個數（深度優先搜尋）

【TSP-GA】基于MATLAB的TSP-GA問題優化仿真