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.

**Prerequisites**:

**Example**:

**Implementation – **Adjacency List and Priority Queue

**Complete Algorithm**:

- 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
and add it to the SPT.*u* - For adjacent vertex v, if v is not in SPT[] and distance[v] > distance[u] + edge u-v
then update*weight*and add it to the priority queue.*distance[v] = distance[u] + edge u-v weight*

- Extract the min node from the priority queue, say it vertex

**Time Complexity:**

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

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

import javafx.util.Pair; | |

import java.util.Comparator; | |

import java.util.LinkedList; | |

import java.util.PriorityQueue; | |

public class DijkstraPQ { | |

static class Edge { | |

int source; | |

int destination; | |

int weight; | |

public Edge(int source, int destination, int weight) { | |

this.source = source; | |

this.destination = destination; | |

this.weight = weight; | |

} | |

} | |

static class Graph { | |

int vertices; | |

LinkedList<Edge>[] adjacencylist; | |

Graph(int vertices) { | |

this.vertices = vertices; | |

adjacencylist = new LinkedList[vertices]; | |

//initialize adjacency lists for all the vertices | |

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

adjacencylist[i] = new LinkedList<>(); | |

} | |

} | |

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

Edge edge = new Edge(source, destination, weight); | |

adjacencylist[source].addFirst(edge); | |

edge = new Edge(destination, source, weight); | |

adjacencylist[destination].addFirst(edge); //for undirected graph | |

} | |

public void dijkstra_GetMinDistances(int sourceVertex){ | |

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

//distance used to store the distance of vertex from a source | |

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

//Initialize all the distance to infinity | |

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

distance[i] = Integer.MAX_VALUE; | |

} | |

//Initialize priority queue | |

//override the comparator to do the sorting based keys | |

PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(vertices, new Comparator<Pair<Integer, Integer>>() { | |

@Override | |

public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) { | |

//sort using distance values | |

int key1 = p1.getKey(); | |

int key2 = p2.getKey(); | |

return key1–key2; | |

} | |

}); | |

//create the pair for for the first index, 0 distance 0 index | |

distance[0] = 0; | |

Pair<Integer, Integer> p0 = new Pair<>(distance[0],0); | |

//add it to pq | |

pq.offer(p0); | |

//while priority queue is not empty | |

while(!pq.isEmpty()){ | |

//extract the min | |

Pair<Integer, Integer> extractedPair = pq.poll(); | |

//extracted vertex | |

int extractedVertex = extractedPair.getValue(); | |

if(SPT[extractedVertex]==false) { | |

SPT[extractedVertex] = true; | |

//iterate through all the adjacent vertices and update the keys | |

LinkedList<Edge> list = adjacencylist[extractedVertex]; | |

for (int i = 0; i < list.size(); i++) { | |

Edge edge = list.get(i); | |

int destination = edge.destination; | |

//only if edge destination is not present in mst | |

if (SPT[destination] == false) { | |

///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 = distance[extractedVertex] + edge.weight ; | |

int currentKey = distance[destination]; | |

if(currentKey>newKey){ | |

Pair<Integer, Integer> p = new Pair<>(newKey, destination); | |

pq.offer(p); | |

distance[destination] = newKey; | |

} | |

} | |

} | |

} | |

} | |

//print Shortest Path Tree | |

printDijkstra(distance, sourceVertex); | |

} | |

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

System.out.println("Dijkstra Algorithm: (Adjacency List + Priority Queue)"); | |

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

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

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

} | |

} | |

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

int vertices = 6; | |

Graph graph = new Graph(vertices); | |

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(0); | |

} | |

} | |

} |

**Output**:

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

Point 7.1 in explanation

“Extract the min node from the heap”

should be

“Extract the min node from the priority queue”