Dijkstra's Algorithm and Flow Chart with Implementation in Java

[1582 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:

Dijkstras algorithm

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

Dijkstras 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
        

Algorithm Logic Test

Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once. 



Need any help in Programming? Chat with Us

Comments



Online Compiler
Search
Algorithm Quiz

Only 5% Users were able to score above 75% in this Quiz. Can You Crack this?

Deals Ends in





Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags

    Dijkstras Algorithm

    Dijkstras Flow Chart

    Dijkstras in Java