## 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 - the path weights from the source s have already been determined. That is for all vertices v ? S; we have d [v] = ? (s, v). The algorithm is made in such a way that it 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.

Image Reference: Geeks for Geeks

## Dijikstras Flow Chart

Image Reference: Geeks for Geeks

# Dijikstras Pseudo Code

1. INITIALIZE - SINGLE - SOURCE (G, s)
2. S??
3. Q?V [G]
4. while Q ? ?
5. do u ? EXTRACT - MIN (Q)
6. S ? S ? {u}
7. for each vertex v ? Adj [u]
8. do RELAX (u, v, w)
## Dijikstras Implementation in Java:

import java.util.*;
import java.lang.*;
import java.io.*;
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 (double 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+" tt "+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 tt 0
1 tt 4
2 tt 12
3 tt 19
4 tt 21
5 tt 11
6 tt 9
7 tt 8
8 tt 14