Nabil Amen
Nabil Amen

Reputation: 69

Multiple paths in Dijkstra's algorithm

I am using Dijksta's method in one of my projects.

My question is how to display all shortest paths from A to B (if they exist). I mean for example if there's more than one path with the same minimal length.

Here is the full code :

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

    @Override
    public String toString() {
        return name;
    }

    @Override
    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 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 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;
    }
}

Upvotes: 2

Views: 3247

Answers (1)

moreON
moreON

Reputation: 2008

You need a set of previous vertices instead of a single vertex. When updating and you find an equal length path, append the vertex to the previous vertex list, clear and replace it on finding a shorter path.

Then processing that to display depends on exactly what you are doing with it. For distinct paths as you have right now, you'll want to recursively traverse the predecessors to generate the set of paths.

Upvotes: 1

Related Questions