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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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