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.
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!
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:
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
You can see a complete example using java 8, recursion and streams -> Dijkstra algorithm with java
Source: Stackoverflow.com