Dijkstra's Algorithm Java, path error when use multiple source

Question

I found Dijkstra's Algorithm from internet (here the original code) , and I try to use multiple source instead multiple destination. But when I run the code, output isn't right, it just shows first vertex for all output.

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

class Vertex implements Comparable<Vertex> {

    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    public int compareTo(Vertex other) {
        return Double.compare(minDistance, other.minDistance);
    }

}

class Edge {

    public final Vertex target;
    public final double weight;

    public Edge(Vertex argTarget, double argWeight) {
        target = argTarget;
        weight = argWeight;
    }

}

public class tes_dijkstra {

    public static void computePaths(Vertex source) {
        source.minDistance = 0.;
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
        vertexQueue.add(source);

        while (!vertexQueue.isEmpty()) {
            Vertex u = vertexQueue.poll();
            // Visit each edge exiting u
            for (Edge e : u.adjacencies) {
                Vertex v = e.target;
                double weight = e.weight;
                double distanceThroughU = u.minDistance + weight;
                if (distanceThroughU < v.minDistance) {
                    vertexQueue.remove(v);
                    v.minDistance = distanceThroughU ;
                    v.previous = u;
                    vertexQueue.add(v);
                }
            }
        }
    }

    public static List<Vertex> getShortestPathTo(Vertex target) {
        List<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        Vertex v0 = new Vertex("Redvile");
        Vertex v1 = new Vertex("Blueville");
        Vertex v2 = new Vertex("Greenville");
        Vertex v3 = new Vertex("Orangeville");
        Vertex v4 = new Vertex("Purpleville");

        v0.adjacencies = new Edge[]{ new Edge(v1, 5),
                                     new Edge(v2, 10),
                                     new Edge(v3, 8) };
        v1.adjacencies = new Edge[]{ new Edge(v0, 5),
                                     new Edge(v2, 3),
                                     new Edge(v4, 7) };
        v2.adjacencies = new Edge[]{ new Edge(v0, 10),
                                     new Edge(v1, 3) };
        v3.adjacencies = new Edge[]{ new Edge(v0, 8),
                                     new Edge(v4, 2) };
        v4.adjacencies = new Edge[]{ new Edge(v1, 7),
                                 new Edge(v3, 2) };
        Vertex[] start = { v1, v2, v3, v4 };
        Vertex[] end ={v2};

        for (int i = 0; i < start.length; i++){
            for(int j = 0; j < end.length; j++){
                computePaths(start[i]);
                System.out.println("Distance to " + end[j] + ": " + end[j].minDistance);
                List<Vertex> path = getShortestPathTo(end[j]);
                System.out.println("Path: " + path);
            }
        }
    }
}

and this is how the output looks like :

Distance to Greenville: 3.0
Path: [Blueville, Greenville]
Distance to Greenville: 0.0
Path: [Blueville, Greenville]
Distance to Greenville: 0.0
Path: [Blueville, Greenville]
Distance to Greenville: 0.0
Path: [Blueville, Greenville]

The output just shows first vertex from Vertex[] start (v1 = Blueville) for all output. I don't know where is wrong, is path stored somewhere? I kinda new in java and I want to learn this algorithm for my assignment, so please help. Thank you

Answer 1

Yes the vertices store information about the cost and the path that is constructed. The problem is not that much that the path itself is constructed but the minDistance is the distance from a given start vertex. You can implement a method reset in the Vertex class

void reset () {
    this.minDistance = Double.POSITIVE_INFINITY;
}

And furthermore you need to reset all vertices of the graph when you want to perform the next Dijkstra's algorithm:

public static List<Vertex> getShortestPathTo(Vertex target) {
    List<Vertex> path = new ArrayList<Vertex>();
    for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
        path.add(vertex);
    Collections.reverse(path);
    return path;
}

public static void main(String[] args) {
    Vertex v0 = new Vertex("Redvile");
    Vertex v1 = new Vertex("Blueville");
    Vertex v2 = new Vertex("Greenville");
    Vertex v3 = new Vertex("Orangeville");
    Vertex v4 = new Vertex("Purpleville");

    v0.adjacencies = new Edge[]{ new Edge(v1, 5),
                                 new Edge(v2, 10),
                                 new Edge(v3, 8) };
    v1.adjacencies = new Edge[]{ new Edge(v0, 5),
                                 new Edge(v2, 3),
                                 new Edge(v4, 7) };
    v2.adjacencies = new Edge[]{ new Edge(v0, 10),
                                 new Edge(v1, 3) };
    v3.adjacencies = new Edge[]{ new Edge(v0, 8),
                                 new Edge(v4, 2) };
    v4.adjacencies = new Edge[]{ new Edge(v1, 7),
                             new Edge(v3, 2) };
    Vertex[] start = { v1, v2, v3, v4 };
    Vertex[] end = {v2};
    Vertex[] all = {v0, v1, v2, v3, v4};

    for (int i = 0; i < start.length; i++){
        for(int j = 0; j < end.length; j++){
            computePaths(start[i]);
            System.out.println("Distance to " + end[j] + ": " + end[j].minDistance);
            List<Vertex> path = getShortestPathTo(end[j]);
            System.out.println("Path: " + path);
        }
        //a new start vertex: reset the graph
        for(Vertex v : all) {
            v.reset();
        }
    }
}