Dijkstra's Algorithm and Flow Chart with Implementation in Java

(190 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.

Dijkstras algorithm

Image Reference: Geeks for Geeks

Dijikstras Flow Chart

Dijkstras 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

Solution Worked 0 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Search

Play 2048 Game Online

Play Duckhunt Online

Need Help?

Looking for any Software or Tutorial?
Don't Worry, we will find it for you
Contact Now

Search Tags

    Dijkstras Algorithm

    Dijkstras Flow Chart

    Dijkstras in Java