How to adapt Dijkstra's algorithm to work with weighted graph

Question

This piece of code works to implement Dijkstra's algorithm for unweighted graph. What should I change to work with a weighted graph? The edges of my graph are double values, there's any chance to use generic types in shortestPath method?

   /**
     * 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's algorithm works with weighted graphs to compute the shortest path from a vertex to all other vertices in a graph provided there are no negative edge lengths in the graph. So there is no need to change the implementation of Dijkstra's to make it work with weighted graph. If it doesn't work with weighted graph then the problem lies with the implementation of Dijkstra.

If the graph is unweighted you are better off using the Breadth first search which runs in linear time to compute the distance between nodes.

Dijkstra's algorithm is a greedy algorithm that works by keeping track of the vertices that has to be expanded ordered by it's cost. i.e. The next vertex that will get expanded is the vertex having the next minimum cost.

This is something we need not do with BFS as all the edge weights are the same. Why use Dijkstra's Algorithm if Breadth First Search (BFS) can do the same thing faster? shows the difference between the both

With your implementation I see you are using a Queue to keep track of the vertices yet to be explored. This does not ensure that the next vertex that is expanded has the minimum cost and thus your algorithm will fail.

So every time you pick a vertex from the Queue to expand it should be the one with the minimum cost. This can be achieved by iterating through the Queue every time and picking up the vertext with minimum cost, although this might reduce it to a O(n^2) algorithm or use heap data structure that ensures that the next picked vertex is always the one with the least weight.

Answer 2

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

The Queue should be a minimum priority queue which means when you do remove operation:

 V vertex = qaux.remove();

This vertex's corresponding distance from the source is the minimum value in this Queue. You can implement a data structure of minimum priority queue by heap.

Answer 3

Thank you for your answers. I already have an implementation working.

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