0 votes
2 views
in Java

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.

## 1 Answer

0 votes
by (26.7k points)

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

0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer
0 votes
1 answer