如何使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)]; 
}