圖的最短路徑和拓撲排序

2019 年 10 月 24 日
筆記

圖的最短路徑

從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑

圖的最短路徑有許多重要的應用。

例如：上圖中v0-v8有9個點，可以看做不同的地點，現在要規划出v0到其它某個點地點的最短路線規劃

構建最短路徑中比較常見的一種演算法即為dijstra(迪傑斯特拉)演算法

dijstra(迪傑斯特拉)演算法

究竟什麼是迪傑斯特拉演算法？它是如何尋找圖中頂點的最短路徑呢？

這個演算法的本質，是不斷刷新起點與其他各個頂點之間的 “距離表”。

讓我們來演示一下迪傑斯特拉的詳細過程：

第1步，創建距離表。表中的Key是頂點名稱，Value是從起點A到對應頂點的已知最短距離。但是，一開始我們並不知道A到其他頂點的最短距離是多少，Value默認是無限大：

第2步，遍歷起點A，找到起點A的鄰接頂點B和C。從A到B的距離是5，從A到C的距離是2。把這一資訊刷新到距離表當中：

第3步，從距離表中找到從A出發距離最短的點，也就是頂點C。

第4步，遍歷頂點C，找到頂點C的鄰接頂點D和F（A已經遍歷過，不需要考慮）。從C到D的距離是6，所以A到D的距離是2+6=8；從C到F的距離是8，所以從A到F的距離是2+8=10。把這一資訊刷新到表中：

接下來重複第3步、第4步所做的操作：

第5步，也就是第3步的重複，從距離表中找到從A出發距離最短的點（C已經遍歷過，不需要考慮），也就是頂點B。

第6步，也就是第4步的重複，遍歷頂點B，找到頂點B的鄰接頂點D和E（A已經遍歷過，不需要考慮）。從B到D的距離是1，所以A到D的距離是5+1=6，小於距離表中的8；從B到E的距離是6，所以從A到E的距離是5+6=11。把這一資訊刷新到表中：

（在第6步，A到D的距離從8刷新到6，可以看出距離表所發揮的作用。距離表通過迭代刷新，用新路徑長度取代舊路徑長度，最終可以得到從起點到其他頂點的最短距離）

第7步，從距離表中找到從A出發距離最短的點（B和C不用考慮），也就是頂點D。

第8步，遍歷頂點D，找到頂點D的鄰接頂點E和F。從D到E的距離是1，所以A到E的距離是6+1=7，小於距離表中的11；從D到F的距離是2，所以從A到F的距離是6+2=8，小於距離表中的10。把這一資訊刷新到表中：

第9步，從距離表中找到從A出發距離最短的點，也就是頂點E。

第10步，遍歷頂點E，找到頂點E的鄰接頂點G。從E到G的距離是7，所以A到G的距離是7+7=14。把這一資訊刷新到表中：

第11步，從距離表中找到從A出發距離最短的點，也就是頂點F。

第10步，遍歷頂點F，找到頂點F的鄰接頂點G。從F到G的距離是3，所以A到G的距離是8+3=11，小於距離表中的14。把這一資訊刷新到表中：

就這樣，除終點以外的全部頂點都已經遍歷完畢，距離表中存儲的是從起點A到所有頂點的最短距離。顯然，從A到G的最短距離是11。（路徑：A-B-D-F-G）

程式碼實現：

/**   * 創建圖   */  public void createGraph(){      int [] a1 = new int[]{0,1,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};      int [] a2 = new int[]{1,0,3,7,5,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};      int [] a3 = new int[]{5,3,0,MAX_WEIGHT,1,7,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};      int [] a4 = new int[]{MAX_WEIGHT,7,MAX_WEIGHT,0,2,MAX_WEIGHT,3,MAX_WEIGHT,MAX_WEIGHT};      int [] a5 = new int[]{MAX_WEIGHT,5,1,2,0,3,6,9,MAX_WEIGHT};      int [] a6 = new int[]{MAX_WEIGHT,MAX_WEIGHT,7,MAX_WEIGHT,3,0,MAX_WEIGHT,5,MAX_WEIGHT};      int [] a7 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,3,6,MAX_WEIGHT,0,2,7};      int [] a8 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,9,5,2,0,4};      int [] a9 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,7,4,0};        matrix[0] = a1;      matrix[1] = a2;      matrix[2] = a3;      matrix[3] = a4;      matrix[4] = a5;      matrix[5] = a6;      matrix[6] = a7;      matrix[7] = a8;      matrix[8] = a9;  }

package cn.itcast.grape;  import cn.itcast.treeandgrape.Graph;    public class JavaDijstra {      private final static int MAXVEX = 9;//頂點，以後不需要寫死      private final static int MAXWEING = 65535;//（最大）權重      private int shortTablePath[] = new int[MAXVEX];//存儲V0到某頂點最短路徑的權值和 例：{0,1,5}        /**       * 獲取一個圖的最短路徑       */      public void shortestPathDijstra(Graph graph) {          int min;//最小值          int k = 0;//記錄下標          boolean isgetPath[] = new boolean[MAXVEX];//是否已經拿到了V0到Vm的最短路徑            for (int v = 0; v < graph.getVertexSize(); v++) {//遍歷頂點數量              shortTablePath[v] = graph.getMatrix()[0][v];//獲得V0這一行的權值數組          }          shortTablePath[0] = 0;//V0到V0的距離是0， 拿到數據後，不必往回走          isgetPath[0] = true;          for (int v = 1; v < graph.getVertexSize(); v++) {//橫向              min = MAXWEING;//初始化              for (int w = 0; w < graph.getVertexSize(); w++) {//縱向，對找出來的頂點一個一個遍歷                  if (!isgetPath[w] && shortTablePath[w] < min) {                      k = w;                      min = shortTablePath[w];                  }              }              isgetPath[k] = true;              for (int j = 0; j < graph.getVertexSize(); j++) {                  if (!isgetPath[j] && (min + graph.getMatrix()[k][j] < shortTablePath[j])) {                      shortTablePath[j] = min + graph.getMatrix()[k][j];                  }              }          }          for (int i = 0; i < shortTablePath.length; i++) {              System.out.println("V0到V" + i + "的最短路徑為：" + shortTablePath[i] + "n");          }      }        public static void main(String[] args) {          Graph graph = new Graph(MAXVEX);          graph.createGraph();          JavaDijstra dijstra = new JavaDijstra();          dijstra.shortestPathDijstra(graph);      }  }

圖的拓撲排序

拓撲排序演算法

思想：從AOV網中選擇一個入度為0的頂點輸出，然後刪除此頂點，並刪除一次頂點為尾的弧，繼續重複該步驟，直至輸出全部頂點或者AOV網中不存在入度為0的頂點為止。

由於拓撲排序需要刪除頂點，所以使用鄰接表的方式存儲圖會較為方便

鄰接表結構

鄰接表的結構不局限於此，可以根據實際情況添加欄位，如在拓撲排序中可以在頂點表中增加入度欄位，用於統計每個頂點的入度情況。在帶權圖中可以在邊表中添加weight欄位，用於表示每條邊的權值。

測試圖：

對應的鄰接表結構：

程式碼實現：

package cn.itcast.grape;    import java.util.Stack;    public class DnGraphTopologic {      private int numVertexes;      private VertexNode[] adjList;//鄰接頂點的一維數組        public DnGraphTopologic(int numVertexes) {          this.numVertexes = numVertexes;      }        private void createGraph() {          VertexNode node0 = new VertexNode(0, "v0");          VertexNode node1 = new VertexNode(0, "v1");          VertexNode node2 = new VertexNode(2, "v2");          VertexNode node3 = new VertexNode(0, "v3");          VertexNode node4 = new VertexNode(2, "v4");          VertexNode node5 = new VertexNode(3, "v5");          VertexNode node6 = new VertexNode(1, "v6");          VertexNode node7 = new VertexNode(2, "v7");          VertexNode node8 = new VertexNode(2, "v8");          VertexNode node9 = new VertexNode(1, "v9");          VertexNode node10 = new VertexNode(1, "v10");          VertexNode node11 = new VertexNode(2, "v11");          VertexNode node12 = new VertexNode(1, "v12");          VertexNode node13 = new VertexNode(2, "v13");          adjList = new VertexNode[numVertexes];          adjList[0] = node0;          adjList[1] = node1;          adjList[2] = node2;          adjList[3] = node3;          adjList[4] = node4;          adjList[5] = node5;          adjList[6] = node6;          adjList[7] = node7;          adjList[8] = node8;          adjList[9] = node9;          adjList[10] = node10;          adjList[11] = node11;          adjList[12] = node12;          adjList[13] = node13;          node0.firstEdge = new EdgeNode(11);          node0.firstEdge.next = new EdgeNode(5);          node0.firstEdge.next.next = new EdgeNode(4);          node1.firstEdge = new EdgeNode(8);          node1.firstEdge.next = new EdgeNode(4);          node1.firstEdge.next.next = new EdgeNode(2);          node2.firstEdge = new EdgeNode(9);          node2.firstEdge.next = new EdgeNode(6);          node2.firstEdge.next.next = new EdgeNode(5);          node3.firstEdge = new EdgeNode(13);          node3.firstEdge.next = new EdgeNode(2);          node4.firstEdge = new EdgeNode(7);          node5.firstEdge = new EdgeNode(12);          node5.firstEdge.next = new EdgeNode(8);          node6.firstEdge = new EdgeNode(5);          node8.firstEdge = new EdgeNode(7);          node9.firstEdge = new EdgeNode(11);          node9.firstEdge.next = new EdgeNode(10);          node10.firstEdge = new EdgeNode(13);          node12.firstEdge = new EdgeNode(9);      }          /**       * 拓撲排序       */        private void topologicalSort() throws Exception {          Stack<Integer> stack = new Stack<>();          int count = 0;//計數，看拓撲排序是不是正確          int k = 0;          for (int i = 0; i < numVertexes; i++) {              if (adjList[i].in == 0) {                  stack.push(i);              }          }            while (!stack.isEmpty()) {              int pop = stack.pop();//彈出棧              System.out.println("頂點：" + adjList[pop].data);              count++;                for (EdgeNode node = adjList[pop].firstEdge; node != null; node = node.next) {//橫向遍歷                  k = node.adjVert;//下標                  if (--adjList[k].in == 0) {                      stack.push(k);//入度為0，入棧                  }              }          }            if (count<numVertexes){              throw new Exception("拓撲排序失敗");          }      }        //邊表頂點（橫）      class EdgeNode {          private int adjVert;//下標          private EdgeNode next;          private int weight;//全重，先看有沒有權重            public EdgeNode(int adjVert) {              this.adjVert = adjVert;          }            public int getAdjVert() {              return adjVert;          }            public void setAdjVert(int adjVert) {              this.adjVert = adjVert;          }            public EdgeNode getNext() {              return next;          }            public void setNext(EdgeNode next) {              this.next = next;          }            public int getWeight() {              return weight;          }            public void setWeight(int weight) {              this.weight = weight;          }      }        //鄰接頂點(縱)      class VertexNode {          private int in;//入度          private String data;          private EdgeNode firstEdge;            public VertexNode(int in, String data) {              this.in = in;              this.data = data;          }      }        public static void main(String[] args) {          DnGraphTopologic dnGraphTopologic = new DnGraphTopologic(14);          dnGraphTopologic.createGraph();          try {              dnGraphTopologic.topologicalSort();          } catch (Exception e) {              e.printStackTrace();          }      }  }