Java - Find shortest path between 2 points in a distance weighted map

Question

Can anyone help me with an algorithm to find the shortest path, I was trying to using Dijkstra's algorithm but, it is not working properly. Below is the rule I want to follow up:

A - B : 10

F - K : 23

R - M : 8

K - O : 40

Z - P : 18

J - K : 25

D - B : 11

M - A : 8

P - R : 15

Any help would be appreciated.

Answer 1

Yes, you can use Dijkstra's Algorithm here, also you can follow the below code for your reference:

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 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)

    {

        // mark all the vertices 

        Vertex A = new Vertex("A");

        Vertex B = new Vertex("B");

        Vertex D = new Vertex("D");

        Vertex F = new Vertex("F");

        Vertex K = new Vertex("K");

        Vertex J = new Vertex("J");

        Vertex M = new Vertex("M");

        Vertex O = new Vertex("O");

        Vertex P = new Vertex("P");

        Vertex R = new Vertex("R");

        Vertex Z = new Vertex("Z");

        // set the edges and weight

        A.adjacencies = new Edge[]{ new Edge(M, 8) };

        B.adjacencies = new Edge[]{ new Edge(D, 11) };

        D.adjacencies = new Edge[]{ new Edge(B, 11) };

        F.adjacencies = new Edge[]{ new Edge(K, 23) };

        K.adjacencies = new Edge[]{ new Edge(O, 40) };

        J.adjacencies = new Edge[]{ new Edge(K, 25) };

        M.adjacencies = new Edge[]{ new Edge(R, 8) };

        O.adjacencies = new Edge[]{ new Edge(K, 40) };

        P.adjacencies = new Edge[]{ new Edge(Z, 18) };

        R.adjacencies = new Edge[]{ new Edge(P, 15) };

        Z.adjacencies = new Edge[]{ new Edge(P, 18) };

        computePaths(A); // run Dijkstra

        System.out.println("Distance to " + Z + ": " + Z.minDistance);

        List<Vertex> path = getShortestPathTo(Z);

        System.out.println("Path: " + path);

    }

}

I hope this will help.

Want to know more about Java? Prefer this tutorial on Learn Java.

Want to become a Java Expert? Join Java Training now!!