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 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 shortest-path tree (SPT) from the given source.
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