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

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