Java - Find shortest path between 2 points in a distance weighted map
Maintain a list of nodes you can travel to, sorted by the distance from your start node. In the beginning only your start node will be in the list.
While you haven't reached your destination: Visit the node closest to the start node, this will be the first node in your sorted list. When you visit a node, add all its neighboring nodes to your list except the ones you have already visited. Repeat!
Like SplinterReality said: There's no reason not to use Dijkstra's algorithm here.
The code below I nicked from here and modified it to solve the example in the question.
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);
}
}
The code above produces:
Distance to Z: 49.0
Path: [A, M, R, P, Z]
Estimated sanjan:
The idea behind Dijkstra's Algorithm is to explore all the nodes of the graph in an ordered way. The algorithm stores a priority queue where the nodes are ordered according to the cost from the start, and in each iteration of the algorithm the following operations are performed:
- Extract from the queue the node with the lowest cost from the start, N
- Obtain its neighbors (N') and their associated cost, which is cost(N) + cost(N, N')
- Insert in queue the neighbor nodes N', with the priority given by their cost
It's true that the algorithm calculates the cost of the path between the start (A in your case) and all the rest of the nodes, but you can stop the exploration of the algorithm when it reaches the goal (Z in your example). At this point you know the cost between A and Z, and the path connecting them.
I recommend you to use a library which implements this algorithm instead of coding your own. In Java, you might take a look to the Hipster library, which has a very friendly way to generate the graph and start using the search algorithms.
Here you have an example of how to define the graph and start using Dijstra with Hipster.
// Create a simple weighted directed graph with Hipster where
// vertices are Strings and edge values are just doubles
HipsterDirectedGraph<String,Double> graph = GraphBuilder.create()
.connect("A").to("B").withEdge(4d)
.connect("A").to("C").withEdge(2d)
.connect("B").to("C").withEdge(5d)
.connect("B").to("D").withEdge(10d)
.connect("C").to("E").withEdge(3d)
.connect("D").to("F").withEdge(11d)
.connect("E").to("D").withEdge(4d)
.buildDirectedGraph();
// Create the search problem. For graph problems, just use
// the GraphSearchProblem util class to generate the problem with ease.
SearchProblem p = GraphSearchProblem
.startingFrom("A")
.in(graph)
.takeCostsFromEdges()
.build();
// Search the shortest path from "A" to "F"
System.out.println(Hipster.createDijkstra(p).search("F"));
You only have to substitute the definition of the graph for your own, and then instantiate the algorithm as in the example.
I hope this helps!
This maybe too late but No one provided a clear explanation of how the algorithm works
The idea of Dijkstra is simple, let me show this with the following pseudocode.
Dijkstra partitions all nodes into two distinct sets. Unsettled and settled. Initially all nodes are in the unsettled set, e.g. they must be still evaluated.
At first only the source node is put in the set of settledNodes. A specific node will be moved to the settled set if the shortest path from the source to a particular node has been found.
The algorithm runs until the unsettledNodes set is empty. In each iteration it selects the node with the lowest distance to the source node out of the unsettledNodes set. E.g. It reads all edges which are outgoing from the source and evaluates each destination node from these edges which are not yet settled.
If the known distance from the source to this node can be reduced when the selected edge is used, the distance is updated and the node is added to the nodes which need evaluation.
Please note that Dijkstra also determines the pre-successor of each node on its way to the source. I left that out of the pseudo code to simplify it.
Credits to Lars Vogel