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.

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

Earn Money by Submitting Articles
Start submutting articles. Click here to get started
Play 2048 Game Online

Play Duckhunt Online
Search Tags

    Dijkstras Algorithm

    Dijkstras Flow Chart

    Dijkstras in Java