# Dijkstra's Algorithm and Flow Chart with Implementation in Java

(282 Views)

## 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