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.

Example:

Dijkstra - Shortest Path Algorithm

Implementation –

Data StructureAdjacency Matrix

Ordering – Searching (Get the vertex with minimum distance among all vertices)

  1. Start with the empty Shortest Path Tree (SPT).
  2. Maintain a set SPT[] to keep track to vertices included in SPT.
  3. 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.
  4. Repeat the following steps until all vertices are processed.
    1. 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.
    2. Add vertex u to SPT[].
    3. Loop over all the adjacent vertices of
    4. 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.

1-32
previous arrow
next arrow
PlayPause
Slider

Complete Code:



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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: