Dijkstra Algorithm

By Priyanshu Vaish|Updated : July 19th, 2022

Dijkstra Algorithm: You may determine the shortest path between two nodes in a graph using Dijkstra Algorithm. In particular, you may create a shortest-path tree by determining the shortest path from a node (referred to as the "source node") to every other node in the graph.

To determine the shortest path between the present location and the destination, GPS devices employ Dijkstra Algorithm. It has several industrial uses, particularly in fields where modelling networks is necessary.

Table of Content

What is the Dijkstra Algorithm?

The single-source shortest path issue for a directed graph G = (V, E) with non-negative edge weights is solved by the greedy algorithm known as the Dijkstra algorithm, which bears the name of its discoverer, Dutch computer scientist Edsger Dijkstra. In other words, we suppose that for any edge (u, v) є E, w(u, v) ≥ 0.

The Dijkstra algorithm maintains a collection of S vertices with predetermined final shortest-path weights from the source. The procedure continually chooses the vertex u є V-S with the least shortest-path estimate, inserts u into S, and relaxes all edges leaving u. In other words, all vertices in S have d[v] = 8(s, v). All the vertices in V-S are kept in a min-priority queue Q that is keyed by their d values. Adjacency lists are used to represent Graph G.

Pseudocode of Dijkstra Algorithm

Every vertex's route distance must be preserved. That can be kept in a v-dimensional array, where v is the total number of vertices. Not only do we want to know how long the shortest path is, but we also want to be able to find it. Each vertex is mapped to the vertex that most recently changed its path length for this purpose.

When the process is finished, we can move backwards to find the path by going from the source vertex to the destination vertex. The vertex with the shortest path distance can be efficiently received using a minimal priority queue.

The pseudocode of Dijkstra algorithm is as follows:

DIJKSTRA (G, w, s)
INITIALIZE-SINGLE-SOURCE (G, s)
S ← Ø
Q ← V[G]
while Q ≠ Ø
do u ← EXTRACT-MIN (Q)
S ← S ∪ (u)
for each vertex v є Adj[u]
do RELAX (u, v, w)

Analysis of Dijkstra Algorithm

The Big-O notation can be used to define the running time of the Dijkstra algorithm as a function of |E| and |V| on a graph with edges and vertices. The Dijkstra algorithm can be implemented in several ways, but its most basic form stores Q's vertices in an ordinary linked list or array, and operation Extract-Min (Q) is just a linear search through all of Q's vertices. The running time in this context is O(|V|2+ |E|) = O(V2).

Dijkstra algorithm can be implemented more effectively for sparse graphs, or graphs with much fewer edges than |V|2, by storing the graph as adjacency lists and utilizing a binary heap or Fibonacci heap as the priority queue to implement the Extract-Min function. When using a binary heap, the algorithm takes O((| E| |V|) time, which is dominated by O(|E| log |V|) when every vertex is assumed to be connected. The Fibonacci heap reduces this time to O(|E| + |V| log |V]).

Example of Dijkstra Algorithm

Consider the directed graph:
byjusexamprep

Find the shortest path from the source vertex A to the other vertices using the Dijkstra algorithm.

Solution:

Dijkstra algorithm maintains a group of S of vertices whose final shortest-path weights from the source have already been determined. The Dijkstra algorithm repeatedly selects the vertex u є V-S with the minimum shortest-path estimate, inserts u into S, and relaxes all edges leaving u. We maintain a min-priority queue Q that contains all the vertices in V – S keyed by their d values.

Initialize:
byjusexamprep

'A' ← EXTRACT-MIN (Q):
byjusexamprep

Relax all edges Leaving 'A' S: {A}
byjusexamprep

'C' ← EXTRACT-MIN(Q):
byjusexamprep

Relax all edges Leaving 'A' S: {A, C}
byjusexamprep

'E' ← EXTRACT-MIN (Q):
byjusexamprep

Relax all edges Leaving 'A' S: {A, C, E}
byjusexamprep

'B' ← EXTRACT-MIN (Q):
byjusexamprep

Relax all, Leaving' A' S: {A, C, E, B}
byjusexamprep

'D' ← EXTRACT-MIN (Q):

byjusexamprep

S: {A, C, E, B, D}

Comments

write a comment

FAQs on Dijkstra Algorithm

  • Any weighted, directed graph with non-negative weights can have its shortest path problem solved by Dijkstra's algorithm. Although it can handle cycles-based graphs, this approach will give false when negative weights are present in the cycle-based graph.

  • In its default configuration, the Dijkstra algorithm determines the shortest path between a beginning node and every connected node. Even in this form, just the vertices of a connected component need to be examined; the other nodes are not visited.

  • Because Dijkstra is so precise, most people favour it over DFS for pathfinding. Dijkstra algorithm discovers the shortest path from the starting position. DFS creates a path that visits every node in the graph; it does not guarantee the shortest path. For weighted graphs, the Dijkstra algorithm determines the shortest path.

  • As we can see, the time complexity is reduced more effectively by Dijkstra's algorithm. But we must use the Bellman-Ford algorithm when the weights are negative. Additionally, the Bellman-Ford technique can assist us in determining if the graph has negative cycles or not.

  • No algorithm, including the Dijkstra algorithm, Bellman-Ford, or Floyd-Warshall, can detect a negative cycle in a graph. The Dijkstra algorithm is greedy, while the others use dynamic programming. Additionally, Dijkstra is ineffective with negative weights even without negative cycles.

Follow us for latest updates