## What is Dijkistras Algorithm?

It is a famous solution for the shortest path problem was given by Dijikstras.It is a greedy algorithm that solves the single-source shortest path problem for a directed graph G = (V, E) with non-negative edge weights, i.e., w(u, v) ≥ 0 for each edge (u, v) Є E.

Dijkstra's Algorithm maintains a set S of vertices whose final shortest - path weights from the source s have already been determined. That's for all vertices v ∈ S; we have d [v] = δ (s, v). The algorithm repeatedly selects the vertex u ∈ V - S with the minimum shortest - path estimate, insert u into S and relaxes all edges leaving u.

Because it always chooses the "lightest" or "closest" vertex in V - S to insert into set S, it is called as the greedy strategy.

#### Example Graph:

Image Reference: Geeks for Geeks

Above Graph will be represented in matrix as:

{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
## Dijikstras Flow Chart

Image Reference: Researchgate

# Dijikstras Pseudo Code

In the pseudocode below:

S = the set of vertices whose shortest path from the source have been found

Q = V-S (at the start of each iteration of the while loop)

DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S = \emptyset
Q = V[G]
while Q \neq \emptyset
do u = EXTRACT-MIN(Q)
S = S \cup {u}
for each vertex v \in Adj[u]
do RELAX(u, v, w)
-------------------------------------
INITIALIZE-SINGLE-SOURCE initializes all the parent variables (pi[v])
to NIL and the shortest distance from the source (d[v]) to infinity.
The distance from s to s (d[s]) is initialized to 0.
INITIALIZE-SINGLE-SOURCE(G, s)
for each vertex v \in V[G]
do d[v] = infinity
pi[v] = NIL
d[s] = 0
-------------------------------------
RELAX tests whether we can improve the shortest path to v
found so far by going through u and, if so, updates d[v] and pi[v].
RELAX(u, v, w)
if d[v] > d[u] + w(u, v)
then d[v] = d[u] + w(u, v)
pi[v] = u
-------------------------------------
## Dijikstras Implementation in Java:

import java.util.*;
import java.lang.*;
import java.io.*;
public class ShortestPath
{
static final int V=9;
int minDistance(int dist[], Boolean sptSet[])
{
int min = Integer.MAX_VALUE, min_index=-1;
//Begining of loop
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
void printSolution(int dist[], int n)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i+" \t\t "+dist[i]);
}
void dijkstra(int graph[][], int src)
{
int dist[] = new int[V];
Boolean sptSet[] = new Boolean[V];
for (int i = 0; i < V; i++)
{
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V-1; count++)
{
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the
// picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an
// edge from u to v, and total weight of path from src to
// v through u is smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist, V);
}
public static void main (String[] args)
{
/* Let us create the example graph discussed above */
int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0);
}
}
#### Output of the above program

Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once.