# 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**:

**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 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
which is not in*u*and has minimum distance. Here we will loop through the vertices and find the vertex with minimum distance.*SPT[]* - Add vertex
to*u**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
then update*weight**distance[v] = distance[u] + edge u-v weight*

- Pick the vertex

**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.

**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