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 adjacency matrix.
We strongly recommend reading – Dijkstra algorithm and how it works.
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 to 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 distance of vertices from the source vertex. Distance of source vertex to 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 u-v weight then update distance[v] = distance[u] + edge u-v 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 over all complexity: O(|V|2).
Please see the animation below for better understanding.
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
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.