Be the first user to complete this post

Add to List 
303. Dijkstra’s – Shortest Path Algorithm (SPT)  Adjacency Matrix  Java Implementation
Earlier we have seen what Dijkstra’s algorithm is and how it works. In this article, we will see its implementation using the adjacency matrix.
brief: What is Dijkstra’s algorithm?
 Dijkstra algorithm is a greedy algorithm.
 It finds a shortest path tree for a weighted undirected graph.
 This means it finds the shortest paths between nodes in a graph, which may represent, for example, road networks
 For a given source node in the graph, the algorithm finds the shortest path between the source node and every other node.
 This algorithm is also used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined.
 Dijkstra’s algorithm is very similar to Prim’s algorithm. In Prim’s algorithm, we create minimum spanning tree (MST) and in the Dijkstra algorithm, we create a shortestpath tree (SPT) from the given source.
Example:
Implementation –
Data Structure  Adjacency Matrix
Ordering – Searching (Get the vertex with minimum distance among all vertices)
 Start with the empty Shortest Path Tree (SPT).
 Maintain a set SPT[] to keep track of vertices included in SPT.
 Assign a distance value to all the vertices, (say distance []) and initialize all the distances with +∞ (Infinity) except the source vertex. This will be used to keep track of the distance of vertices from the source vertex. Distance of source vertex to the source vertex will be 0.
 Repeat the following steps until all vertices are processed.
 Pick the vertex u which is not in SPT[] and has minimum distance. Here we will loop through the vertices and find the vertex with minimum distance.
 Add vertex u to SPT[].
 Loop over all the adjacent vertices of
 For adjacent vertex v, if v is not in SPT[] and distance[v] > distance[u] + edge uv weight then update distance[v] = distance[u] + edge uv weight
Time Complexity: O(V^{2}).
Total vertices: V, Total Edges : E
 O(V) – Iterate through all vertices to add them in SPT
 O(V) – Each time select a vertex with minimum distance.
 So overall complexity: O(V^{2}).
Please see the animation below for better understanding.
Output:
Dijkstra Algorithm: (Adjacency Matrix) Source Vertex: 0 to vertex 0 distance: 0 Source Vertex: 0 to vertex 1 distance: 4 Source Vertex: 0 to vertex 2 distance: 3 Source Vertex: 0 to vertex 3 distance: 6 Source Vertex: 0 to vertex 4 distance: 8 Source Vertex: 0 to vertex 5 distance: 14