java - 如何使 Dijkstra 算法适应加权图

Question

这段代码用于实现未加权图的 Dijkstra 算法。我应该更改什么才能使用加权图？我的图的边是 double 值，是否有机会在 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 并以最小成本选取顶点来实现，尽管这可能会将其减少到 O(n^2) 算法或使用堆数据结构，确保下一个选取的顶点始终是权重最小的顶点。