Dijkstra`s Algorithm

Posted By on September 18, 2014


Download PDF
Greedy Solution to the Fractional Knapsack Problem
Job Scheduling Algorithm by Greedy Method

Dijkstra’s algorithm, conceived by computer scientist Edsger Dijkstra in 1956 and published in 1959,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. This algorithm is often used in routing and as a subroutine in other graph algorithms.

For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path algorithm is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).

Dijkstra’s original algorithm does not use a min-priority queue and runs in time O(|V|^2) (where |V| is the number of vertices). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E|+|V|log|V|) (where |E| is the number of edges) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.

Note that graphs under special cases such as integer and/or bounded weights, can be improved further in complexity. See the following section on running time.

 

Algorithm

Illustration of Dijkstra’s algorithm search for finding path from a start node (lower left, red) to a goal node (upper right, green) in a robot motion planning problem. Open nodes represent the “tentative” set. Filled nodes are visited ones, with color representing the distance: the greener, the farther. Nodes in all the different directions are explored uniformly, appearing as a more-or-less circular wavefront as Dijkstra’s algorithm uses a heuristic identically equal to 0.

Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step.

  1. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
  2. 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.
  3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. 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. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.
  4. 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.
  5. 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.
  6. 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.

Pseudocode

In the following algorithm, the code u := vertex in Q with min dist[u], searches for the vertex u in the vertex set Q that has the least dist[u] value. length(u, v) returns the length of the edge joining (i.e. the distance between) the two neighbor-nodes u and v. The variable alt on line 17 is the length of the path from the root node to the neighbor node v if it were to go through u. If this path is shorter than the current shortest path recorded for v, that current path is replaced with this alt path. The previous array is populated with a pointer to the “next-hop” node on the source graph to get the shortest route to the source.

 1  function Dijkstra(Graph, source):
 2      dist[source]  := 0                     // Distance from source to source
 3      for each vertex v in Graph:            // Initializations
 4          if vsource
 5              dist[v]  := infinity           // Unknown distance function from source to v
 6              previous[v]  := undefined      // Previous node in optimal path from source
 7          end if
 8          add v to Q                         // All nodes initially in Q (unvisited nodes)
 9      end for
10
11      while Q is not empty:                  // The main loop
12          u := vertex in Q with min dist[u]  // Source node in first case
13          remove u from Q
14
15          for each neighbor v of u:           // where v has not yet been removed from Q.
16              alt := dist[u] + length(u, v)
17              if alt < dist[v]:               // A shorter path to v has been found
18                  dist[v]  := alt
19                  previous[v]  := u
20              end if
21          end for
22      end while
23      return dist[], previous[]
24  end function

If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 13 if u = target. Now we can read the shortest path from source to target by reverse iteration:

1  S := empty sequence
2  u := target
3  while previous[u] is defined:                // Construct the shortest path with a stack S
4      insert u at the beginning of S           // Push the vertex into the stack
5      u := previous[u]                         // Traverse from target to source
6  end while

Now sequence S is the list of vertices constituting one of the shortest paths from source to target, or the empty sequence if no path exists.

A more general problem would be to find all the shortest paths between source and target (there might be several different ones of the same length). Then instead of storing only a single node in each entry of previous[] we would store all nodes satisfying the relaxation condition. For example, if both r and source connect to target and both of them lie on different shortest paths through target (because the edge cost is the same in both cases), then we would add both r and source to previous[target]. When the algorithm completes, previous[] data structure will actually describe a graph that is a subset of the original graph with some edges removed. Its key property will be that if the algorithm was run with some starting node, then every path from that node to any other node in the new graph will be the shortest path between those nodes in the original graph, and all paths of that length from the original graph will be present in the new graph. Then to actually find all these shortest paths between two given nodes we would use a path finding algorithm on the new graph, such as depth-first search.

Running time

An upper bound of the running time of Dijkstra’s algorithm on a graph with edges E and vertices V can be expressed as a function of |E| and |V| using big-O notation.

For any implementation of vertex set Q the running time is in O(|E| cdot dk_Q + |V| cdot em_Q), where dk_Q and em_Q are times needed to perform decrease key and extract minimum operations in set Q, respectively.

The simplest implementation of the Dijkstra’s algorithm stores vertices of set Q in an ordinary linked list or array, and extract minimum from Q is simply a linear search through all vertices in Q. In this case, the running time is O(|E| + |V|^2) = O(|V|^2).

For sparse graphs, that is, graphs with far fewer than O(|V|^2) edges, Dijkstra’s algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap as a priority queue to implement extracting minimum efficiently. With a self-balancing binary search tree or binary heap, the algorithm requires Theta((|E| + |V|) log |V|) time (which is dominated by Theta( | E | log | V | ), assuming the graph is connected). To avoid O(|V|) look-up in decrease-key step on a vanilla binary heap, it is necessary to maintain a supplementary index mapping each vertex to the heap’s index (and keep it up to date as priority queue Q changes), making it take only O(log|V|) time instead. The Fibonacci heap improves this to O(|E| + |V| log|V|).

Various special cases can indeed be improved further.

When arc weights are integers and bounded by a constant C, the usage of a special priority queue structure by Van Emde Boas etal.(1977) (Ahuja et al. 1990) brings the complexity to O(|E|loglog|C|). Another interesting implementation based on a combination of a new Radix-heap and the well-known Fibonacci-heap runs in O(|E|+|V|sqrt{log|C|}) complexity (Ahuja et al. 1990). Finally, the best algorithms in this special case are as follows. The algorithm given by (Thorup 2000) runs in O(|E|loglog|V|) time and the algorithm given by (Raman 1997) runs in O(|E| + |V|min{(log|V|)^{1/3+epsilon}, (log|C|)^{1/4+epsilon}}) time.

Also, for directed acyclic graphs, it is possible to find shortest paths from a given starting vertex in linear O(|E|+|V|) time, by processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum length obtained via any of its incoming edges.[4] [5]

In the special case of integer weights and undirected graphs, the Dijkstra’s algorithm can be completely countered with a linear O(|V|+|E|) complexity algorithm

 

Greedy Solution to the Fractional Knapsack Problem
Job Scheduling Algorithm by Greedy Method

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com