Earlier we have seen what Dijkstra’s algorithm is and how it works. In this article, we will see its implementation using the adjacency list and Priority Queue.
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 a shortest-path tree (SPT) from the given source.
Implementation – Adjacency List and Priority Queue
- Create priority queue of size = no of vertices.
- Will create pair object for each vertex with two information’s, vertex and distance. (similar to heap node)
- Override the Comparator of priority queue to sort them based on the key
- Use SPT to keep track of the vertices which are currently in Shortest Path Tree(SPT).
- Create distance  to keep track of distance for each vertex from the source. , initialize all distances as MAX_VAL except the first vertex for which distance will 0. (Start from first vertex).
- Create a pair object for vertex 0 with distance 0 and insert into priority queue.
- while priority queue is not empty
- Extract the min node from the priority queue, say it vertex u and add it to the SPT.
- 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 and add it to the priority queue.
Total vertices: V, Total Edges: E
- O(logV) – to extract each vertex from queue. So for V vertices – O(VlogV)
- O(logV) – each time new pair object with new key value of a vertex and will be done for at most once for each edge. So for total E edge – O(ElogV)
- So over all complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
See the animation below for more understanding
Dijkstra Algorithm: (Adjacency List + Priority Queue) 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