如何使Dijkstra的算法適用於加權圖

Question

這段代碼用於實現Dijkstra的未加權圖的算法。我應該改變什麼來使用加權圖？我的圖的邊緣是雙值，有沒有機會在shortestPath方法中使用泛型類型？

/** 
    * Determine the shortest path to all vertices from a vertex using Dijkstra's algorithm 
    * To be called by public short method 
    * 
    * @param graph Graph object 
    * @param sourceIdx Source vertex 
    * @param knownVertices previously discovered vertices 
    * @param verticesIndex index of vertices in the minimum path 
    * @param minDist minimum distances in the path 
    * 
    */ 
    private static <V> void shortestPath(AdjacencyMatrixGraph<V,Double> graph, int sourceIdx, boolean[] knownVertices, int[] verticesIndex, double [] minDist) { 
     V vertexOrig = graph.vertices.get(sourceIdx); 
     Queue<V> qaux = new LinkedList<V>(); 
     for(int i = 0; i < graph.numVertices; i++) { 
      minDist[i] = 0; 
      verticesIndex[i] = -1; 
     } 
     qaux.add(vertexOrig); 
     while(!qaux.isEmpty()) { 
      V vertex = qaux.remove(); 
      for (V vertexAdj: graph.directConnections(vertex)) { 
       if(minDist[graph.toIndex(vertexAdj)] == 0) { 
        minDist[graph.toIndex(vertexAdj)] = minDist[graph.toIndex(vertex)] 
          + graph.getEdge(vertex, vertexAdj); 
        verticesIndex[graph.toIndex(vertexAdj)] = graph.toIndex(vertex); 
        qaux.add(vertexAdj); 
       } 
      } 
     } 
    } 


    /** 
    * Determine the shortest path between two vertices using Dijkstra's algorithm 
    * 
    * @param graph Graph object 
    * @param source Source vertex 
    * @param dest Destination vertices 
    * @param path Returns the vertices in the path (empty if no path) 
    * @return minimum distance, -1 if vertices not in graph or no path 
    * 
    */ 
    public static <V> double shortestPath(AdjacencyMatrixGraph<V, Double> graph, V source, V dest, LinkedList<V> path){ 
     path.clear(); 
     if(!graph.checkVertex(source) || !graph.checkVertex(dest)) return -1; 
     else if(source.equals(dest)) { 
      path.add(dest); 
      return 0; 
     } 
     double minDist[] = new double[graph.numVertices]; 
     int verticesIndex[] = new int[graph.numVertices]; 

     shortestPath(graph, graph.toIndex(source), new boolean[graph.numVertices] 
     , verticesIndex, minDist); 

     if(verticesIndex[graph.toIndex(source)] == -1 || verticesIndex[graph.toIndex(dest)] == -1) return -1; 

     recreatePath(graph, graph.toIndex(source), graph.toIndex(dest), verticesIndex, path); 
     Collections.reverse(path); 
     System.out.println(path); 
     System.out.println(minDist[graph.toIndex(dest)]); 
     return minDist[graph.toIndex(dest)]; 
    } 


    /** 
    * Recreates the minimum path between two vertex, from the result of Dikstra's algorithm 
    * 
    * @param graph Graph object 
    * @param sourceIdx Source vertex 
    * @param destIdx Destination vertices 
    * @param verticesIndex index of vertices in the minimum path 
    * @param Queue Vertices in the path (empty if no path) 
    */ 
    private static <V> void recreatePath(AdjacencyMatrixGraph<V, Double> graph, int sourceIdx, int destIdx, int[] verticesIndex, LinkedList<V> path){ 

     path.add(graph.vertices.get(destIdx)); 
     if (sourceIdx != destIdx){ 
      destIdx = verticesIndex[destIdx];   
      recreatePath(graph, sourceIdx, destIdx, verticesIndex, path); 
     } 
    } 

Answer 1

Dijkstra算法與加權曲線工作以從頂點到在圖中的所有其他頂點計算的最短路徑提供有在圖中沒有負的邊緣長度。所以不需要改變Dijkstra的實現來使它與加權圖一起工作。如果它不適用於加權圖，那麼問題在於Dijkstra的實現。

如果圖形未加權，則最好使用以線性時間運行的寬度優先搜索來計算節點之間的距離。

Dijkstra算法是一種貪心算法，它通過跟蹤需要擴展的頂點來控制其成本。即將要擴展的下一個頂點是具有下一個最小成本的頂點。

這是我們不需要用BFS做的事情，因爲所有的邊權重都是一樣的。 Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster?顯示了兩者之間的差異

在您的實施中，我看到您正在使用Queue來跟蹤尚未探索的頂點。這並不能確保展開的下一個頂點的成本最小，因此算法將失敗。

因此，每當您從Queue中挑選一個頂點來展開時，它應該是成本最低的頂點。這可以通過迭代遍歷Queue並以最小代價獲取vertext來實現，儘管這可能會將其減少到O(n^2)算法，或者使用堆數據結構來確保下一個拾取的頂點總是具有最小權重的頂點。

Answer 2

Queue<V> qaux = new LinkedList<V>(); 

隊列最小應爲優先級隊列，這意味着，當你刪除操作：

V vertex = qaux.remove(); 

此頂點的從源相應的距離是在此隊列中的最小值。您可以通過堆實現最小優先級隊列的數據結構。

Answer 3

謝謝你的回答。我已經有一個實施工作。

private static <V> void shortestPath(AdjacencyMatrixGraph<V,Double> graph, int sourceIdx, boolean[] knownVertices, int[] verticesIndex, double [] minDist) { 
    V vertexOrig = graph.vertices.get(sourceIdx); 
    for(int i = 0; i < graph.numVertices; i++) { 
     minDist[i] = Double.MAX_VALUE; 
     verticesIndex[i] = -1; 
     knownVertices[i] = false; 
    } 
    verticesIndex[sourceIdx] = 0; 
    minDist[sourceIdx] = 0; 
    while(sourceIdx != -1) { 
     knownVertices[sourceIdx] = true; 
     for (V vertexAdj: graph.directConnections(vertexOrig)) { 
      int adjIdx = graph.toIndex(vertexAdj); 
      if(!knownVertices[adjIdx] 
        && (minDist[adjIdx] > (minDist[sourceIdx] + graph.getEdge(vertexOrig, vertexAdj)))) { 
       minDist[adjIdx] = minDist[sourceIdx] + graph.getEdge(vertexOrig, vertexAdj); 
       verticesIndex[adjIdx] = sourceIdx; 
      } 
     } 
     double min = Double.MAX_VALUE; 
     sourceIdx = -1; 
     for(int i = 0; i < minDist.length; i++) { 
      if(minDist[i] < min && !knownVertices[i]) { 
       min = minDist[i]; 
       sourceIdx = i; 
       vertexOrig = graph.vertices.get(sourceIdx); 
      } 
     } 
    } 
} 


public static <V> double shortestPath(AdjacencyMatrixGraph<V, Double> graph, V source, V dest, LinkedList<V> path){ 
    path.clear(); 
    if(!graph.checkVertex(source) || !graph.checkVertex(dest)) return -1; 
    else if(source.equals(dest)) { 
     path.add(dest); 
     return 0; 
    } 
    double minDist[] = new double[graph.numVertices]; 
    int verticesIndex[] = new int[graph.numVertices]; 
    int sourceIdx = graph.toIndex(source); 

    shortestPath(graph, graph.toIndex(source), new boolean[graph.numVertices] 
    , verticesIndex, minDist); 

    if(verticesIndex[sourceIdx] == -1) return -1; 

    recreatePath(graph, graph.toIndex(source), graph.toIndex(dest), verticesIndex, path); 
    Collections.reverse(path); 

    return minDist[graph.toIndex(dest)]; 
}