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

Question

I need an algorithm to find shortest path between two points in a map where road distance is indicated by a number   what is given  Start 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 shortest distance to all destinations  not just one   Any suggestion is appreciated

User · Answer

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!

User · Answer

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 lt Vertex gt        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 lt Vertex gt  vertexQueue   new PriorityQueue lt Vertex gt             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  lt  v minDistance                        vertexQueue remove v                        v minDistance   distanceThroughU                       v previous   u                      vertexQueue add v                                                        public static List lt Vertex gt  getShortestPathTo Vertex target                List lt Vertex gt  path   new ArrayList lt Vertex gt             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 lt Vertex gt  path   getShortestPathTo Z           System out println  Path      path             The code above produces   Distance to Z  49 0 Path   A  M  R  P  Z

User · Answer

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

User · Answer

You can see a complete example using java 8  recursion and streams -  Dijkstra algorithm with java

User · Answer

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 lt String Double gt  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

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

Examples related to java

Examples related to path

Examples related to shortest