Dijkstra's Dilema：我怎樣才能讓我的算法摘要？

Question

我在做代碼的力量，並希望實現Dijkstra的最短路徑算法用於使用帶有鄰接矩陣的Java的有向圖，但是我很難使它適用於其編碼處理的其他尺寸。

這是我工作的代碼

int max = Integer.MAX_VALUE;//substitute for infinity 

    int[][] points={//I used -1 to denote non-adjacency/edges 
      //0, 1, 2, 3, 4, 5, 6, 7 
      {-1,20,-1,80,-1,-1,90,-1},//0 
      {-1,-1,-1,-1,-1,10,-1,-1},//1 
      {-1,-1,-1,10,-1,50,-1,20},//2 
      {-1,-1,-1,-1,-1,-1,20,-1},//3 
      {-1,50,-1,-1,-1,-1,30,-1},//4 
      {-1,-1,10,40,-1,-1,-1,-1},//5 
      {-1,-1,-1,-1,-1,-1,-1,-1},//6 
      {-1,-1,-1,-1,-1,-1,-1,-1} //7 
      }; 
    int [] record = new int [8];//keeps track of the distance from start to each node 
    Arrays.fill(record,max); 
    int sum =0;int q1 = 0;int done =0; 
    ArrayList<Integer> Q1 = new ArrayList<Integer>();//nodes to transverse 
    ArrayList<Integer> Q2 = new ArrayList<Integer>();//nodes collected while transversing 
    Q1.add(0);//starting point 
    q1= Q1.get(0); 
    while(done<9) {// <<< My Problem 
     for(int q2 = 1; q2<8;q2++) {//skips over the first/starting node 
      if(points[q1][q2]!=-1) {//if node is connected by an edge 
       if(record[q1] == max)//never visited before 
        sum=0; 
       else 
        sum=record[q1];//starts from where it left off 
       int total = sum+points[q1][q2];//total distance of route 
       if(total < record[q2])//connected node distance 
        record[q2]=total;//if smaller 
       Q2.add(q2);//colleceted node 
      } 
     } 
     done++; 
     Q1.remove(0);//removes the first node because it has just been used 
     if(Q1.size()==0) {//if there are no more nodes to transverse 
      Q1=Q2;//Pours all the collected connecting nodes to Q1 
      Q2= new ArrayList<Integer>(); 
      q1=Q1.get(0); 
     } 
     else// 
      q1=Q1.get(0);//sets starting point 
    }![enter image description here][1] 

然而，我的算法的版本只工作，因爲我設置了while循環的解決答案。換句話說，它只適用於這個問題/圖表，因爲我先用手解決了它。

我怎樣才能讓它適用於所有規模的團體？

這裏是例子的圖形表達圖我的問題是基於：

Answer 1

我認爲你正在尋找的主要答案是，你應該讓while循環運行，直到Q1是空。你所做的實質上是一個最好的搜索。雖然需要更多更改，因爲您的代碼有點不正統。

通常，Dijkstra算法與優先級隊列一起使用。根據我的理解，Q1是您的「待辦事項列表」。 Dijkstra's的規範說，最接近起始頂點的頂點應該在下一步探索，所以您應該使用Q1的PriorityQueue來對頂點進行排序，根據頂點最接近起始頂點。最常見的Java實現使用PriorityQueue和一個元組類：內部類存儲對頂點的引用和到起始頂點的「距離」。 Dijkstra的規範還規定，如果發現一個新的邊緣使得頂點更接近起點，則應該在優先級隊列中的條目上使用DecreaseKey操作，以使頂點更早出現（因爲它現在更近了） 。但是，由於PriorityQueue不支持該操作，因此會在隊列中添加一個全新的條目。如果你有一個支持這個操作的堆（我自己創建了一個，here），那麼reduceKey可以顯着提高效率，因爲你不需要再創建那些元組。

所以我希望這是一個足夠的答案然後：做一個適當的'待辦事項'列表，而不是Q1，並使算法通用，讓while循環運行，直到待辦事項列表爲空。

編輯：我讓您根據自己的格式，似乎工作的落實：

public void run() { 
    final int[][] points = { //I used -1 to denote non-adjacency/edges 
     //0, 1, 2, 3, 4, 5, 6, 7 
     {-1,20,-1,80,-1,-1,90,-1}, //0 
     {-1,-1,-1,-1,-1,10,-1,-1}, //1 
     {-1,-1,-1,10,-1,50,-1,20}, //2 
     {-1,-1,-1,-1,-1,-1,20,-1}, //3 
     {-1,50,-1,-1,-1,-1,30,-1}, //4 
     {-1,-1,10,40,-1,-1,-1,-1}, //5 
     {-1,-1,-1,-1,-1,-1,-1,-1}, //6 
     {-1,-1,-1,-1,-1,-1,-1,-1} //7 
    }; 
    final int[] result = dijkstra(points,0); 
    System.out.print("Result:"); 
    for(final int i : result) { 
     System.out.print(" " + i); 
    } 
} 

public int[] dijkstra(final int[][] points,final int startingPoint) { 
    final int[] record = new int[points.length]; //Keeps track of the distance from start to each vertex. 
    final boolean[] explored = new boolean[points.length]; //Keeps track of whether we have completely explored every vertex. 
    Arrays.fill(record,Integer.MAX_VALUE); 
    final PriorityQueue<VertexAndDistance> todo = new PriorityQueue<>(points.length); //Vertices left to traverse. 
    todo.add(new VertexAndDistance(startingPoint,0)); //Starting point (and distance 0). 
    record[startingPoint] = 0; //We already know that the distance to the starting point is 0. 
    while(!todo.isEmpty()) { //Continue until we have nothing left to do. 
     final VertexAndDistance next = todo.poll(); //Take the next closest vertex. 
     final int q1 = next.vertex; 
     if(explored[q1]) { //We have already done this one, don't do it again. 
      continue; //...with the next vertex. 
     } 

     for(int q2 = 1;q2 < points.length;q2++) { //Find connected vertices. 
      if(points[q1][q2] != -1) { //If the vertices are connected by an edge. 
       final int distance = record[q1] + points[q1][q2]; 
       if(distance < record[q2]) { //And it is closer than we've seen so far. 
        record[q2] = distance; 
        todo.add(new VertexAndDistance(q2,distance)); //Explore it later. 
       } 
      } 
     } 

     explored[q1] = true; //We're done with this vertex now. 
    } 
    return record; 
} 

private class VertexAndDistance implements Comparable<VertexAndDistance> { 
    private final int distance; 
    private final int vertex; 

    private VertexAndDistance(final int vertex,final int distance) { 
     this.vertex = vertex; 
     this.distance = distance; 
    } 

    /** 
    * Compares two {@code VertexAndDistance} instances by their distance. 
    * @param other The instance with which to compare this instance. 
    * @return A positive integer if this distance is more than the distance 
    * of the specified object, a negative integer if it is less, or 
    * {@code 0} if they are equal. 
    */ 
    @Override 
    public int compareTo(final VertexAndDistance other) { 
     return Integer.compare(distance,other.distance); 
    } 
} 

輸出：0 20 40 50 2147483647 30 70 60