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

[19110 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 - 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); } }