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

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