Java - find the shortest path between two points on a map with distance

Question

I need an algorithm to find the shortest path between two points on the map where the road distance is indicated by a number.

what is given: Start of city A Destination city Z

List of distances between cities:

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

I thought I could use Dijkstra's algorithm, however it finds the shortest distance to all destinations. not just one.

Any suggestion is appreciated.

Answer 1

As SplinterReality said: There no reason not to use Dijkstra algorithm here.

I added the code below 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 above code produces:

 Distance to Z: 49.0 Path: [A, M, R, P, Z] 

Answer 2

Estimated Sanjan:

The idea of ​​Dijkstra's algorithm is to examine all nodes of the graph in an orderly manner. The algorithm stores the priority queue, where the nodes are ordered according to the costs from the very beginning, and at each iteration of the algorithm the following operations are performed:

• Remove from the queue the lowest cost node from the start, N
• Get your neighbors (N ') and their corresponding cost, cost (N) + cost (N, N')
• Insert neighboring nodes N 'into the queue, with priority indicated by their cost

It is true that the algorithm calculates the cost of the path between the start (A in your case) and all the other nodes, but you can stop exploring 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 that you use a library that implements this algorithm instead of encoding your own. In Java, you can take a look at the Hipster library , which has a very convenient way to generate graphs and start using search algorithms.

Here you have an example of how to define a schedule 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 need to substitute the definition of the graph for your own, and then create an instance of the algorithm, as in the example.

Hope this helps!

Answer 3

It may be too late, but no one has given a clear explanation of how the algorithm works.

Dijkstra's idea is simple, let me show it with the following pseudo-code.

Dijkstra splits all nodes into two different sets. Unsettled and settled. Initially, all nodes are in an uninstalled set, for example. they should still be appreciated.

First, only the node set is placed in the settNodes set. The specific node will be moved to the installed set if the shortest path from the source to the specific node is found.

The algorithm runs until the set unsettledNodes is empty. At each iteration, the node with the smallest distance to the source node is selected from the unsettledNodes set. For example. It reads all the edges coming from the source and evaluates each node destination from those edges that are not yet set.

If the known distance from the source to this node can be reduced by using the selected edge, the distance is updated, and the node is added to the nodes that need to be evaluated.

Note that Dijkstra also defines the successor to each node along the source path. I left this from the pseudo code to simplify it.

Loans Lars Vogel

Answer 4

Maintain a list of nodes you can navigate to, sorted by distance from your launch node. At the beginning, only your start node will be listed.

Until you reach your goal: Visit the node closest to the beginning of the node, this will be the first node in your sorted list. When you visit a node, add all of your neighboring nodes to your list, except those that you have already visited. Repeat!

Answer 5

You can see the full example using Java 8, recursion and threads -> Dijkstra's algorithm with Java