Dijkstra's Algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. Concieved by Edsger Dijkstra.

- Both directed and undirected graphs
- All edges must have nonnegative weights
- Graph must be connected

- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
- Mark all nodes unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes.
- For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8.
- When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
- If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
- Select the unvisited node that is marked with the smallest tentative distance, and set it as the new "current node" then go back to step 3.

Edsger Dijkstra's parents were Douwe Wybe Dijkstra and Brechtje Cornelia Kluijver (or Kluyver); he was the third of their four children. His father taught chemistry at the high school in Rotterdam while his mother was trained as a mathematician although she never had a formal position. Dijkstra wrote later of his mother's mathematical influence on him "she had a great agility in manipulating formulae and a wonderful gift for finding very elegant solutions".He published this shortest distance algorithm, together with his very efficient algorithm for the shortest spanning tree, were published in the two page paper A Note on Two Problems in Connexion with Graphs (1959). Also in 1959 he was awarded his Ph.D. from the University of Amsterdam for his thesis Communication with an Automatic Computer

Download PDFEvery time the main loop executes, one vertex is extracted from the queue. Assuming that there are V vertices in the graph, the queue may contain O(V) vertices. Each pop operation takes O(log V) time assuming the heap implementation of priority queues. So the total time required to execute the main loop itself is O(V log V). In addition, we must consider the time spent in the function expand, which applies the function handle_edge to each outgoing edge. Because expand is only called once per vertex, handle_edge is only called once per edge. It might call push(v'), but there can be at most V such calls during the entire execution, so the total cost of that case arm is at most O(V log V). The other case arm may be called O(E) times, however, and each call to increase_priority takes O(log V) time with the heap implementation. Therefore the total run time is O(V log V + E log V), which is O(E log V) because V is O(E) assuming a connected graph.

(There is another more complicated priority-queue implementation called a Fibonacci heap that implements increase_priority in O(1) time, so that the asymptotic complexity of Dijkstra's algorithm becomes O(V log V + E); however, large constant factors make Fibonacci heaps impractical for most uses.)

O(|E|+|V|log|V|)

Dijkstra shortest path algorithm. How to find least-cost or minimum cost paths in a graph using Dijkstra's Algorithm. Show the shortest path or minimum cost from node/vertices A to node/vertices F.

Download PDFimport java.util.PriorityQueue; import java.util.List; import java.util.ArrayList; import java.util.Collections; class Vertex implements Comparable{ 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 vertexQueue = new PriorityQueue (); 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 getShortestPathTo(Vertex target) { List path = new ArrayList (); 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 path = getShortestPathTo(Z); System.out.println("Path: " + path); } }