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

public class DijkstraAdjacencyMatrix { | |

static class Graph{ | |

int vertices; | |

int matrix[][]; | |

public Graph(int vertex) { | |

this.vertices = vertex; | |

matrix = new int[vertex][vertex]; | |

} | |

public void addEdge(int source, int destination, int weight) { | |

//add edge | |

matrix[source][destination]=weight; | |

//add back edge for undirected graph | |

matrix[destination][source] = weight; | |

} | |

//get the vertex with minimum distance which is not included in SPT | |

int getMinimumVertex(boolean [] mst, int [] key){ | |

int minKey = Integer.MAX_VALUE; | |

int vertex = –1; | |

for (int i = 0; i <vertices ; i++) { | |

if(mst[i]==false && minKey>key[i]){ | |

minKey = key[i]; | |

vertex = i; | |

} | |

} | |

return vertex; | |

} | |

public void dijkstra_GetMinDistances(int sourceVertex){ | |

boolean[] spt = new boolean[vertices]; | |

int [] distance = new int[vertices]; | |

int INFINITY = Integer.MAX_VALUE; | |

//Initialize all the distance to infinity | |

for (int i = 0; i <vertices ; i++) { | |

distance[i] = INFINITY; | |

} | |

//start from the vertex 0 | |

distance[sourceVertex] = 0; | |

//create SPT | |

for (int i = 0; i <vertices ; i++) { | |

//get the vertex with the minimum distance | |

int vertex_U = getMinimumVertex(spt, distance); | |

//include this vertex in SPT | |

spt[vertex_U] = true; | |

//iterate through all the adjacent vertices of above vertex and update the keys | |

for (int vertex_V = 0; vertex_V <vertices ; vertex_V++) { | |

//check of the edge between vertex_U and vertex_V | |

if(matrix[vertex_U][vertex_V]>0){ | |

//check if this vertex 'vertex_V' already in spt and | |

// if distance[vertex_V]!=Infinity | |

if(spt[vertex_V]==false && matrix[vertex_U][vertex_V]!=INFINITY){ | |

//check if distance needs an update or not | |

//means check total weight from source to vertex_V is less than | |

//the current distance value, if yes then update the distance | |

int newKey = matrix[vertex_U][vertex_V] + distance[vertex_U]; | |

if(newKey<distance[vertex_V]) | |

distance[vertex_V] = newKey; | |

} | |

} | |

} | |

} | |

//print shortest path tree | |

printDijkstra(sourceVertex, distance); | |

} | |

public void printDijkstra(int sourceVertex, int [] key){ | |

System.out.println("Dijkstra Algorithm: (Adjacency Matrix)"); | |

for (int i = 0; i <vertices ; i++) { | |

System.out.println("Source Vertex: " + sourceVertex + " to vertex " + + i + | |

" distance: " + key[i]); | |

} | |

} | |

} | |

public static void main(String[] args) { | |

int vertices = 6; | |

Graph graph = new Graph(vertices); | |

int sourceVertex = 0; | |

graph.addEdge(0, 1, 4); | |

graph.addEdge(0, 2, 3); | |

graph.addEdge(1, 2, 1); | |

graph.addEdge(1, 3, 2); | |

graph.addEdge(2, 3, 4); | |

graph.addEdge(3, 4, 2); | |

graph.addEdge(4, 5, 6); | |

graph.dijkstra_GetMinDistances(sourceVertex); | |

} | |

} |

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