Shortest path using Dijkstra's algorithm

Dijkstra’s algorithm is an algorithm to find the shortest paths from source node to other nodes in a weighted graph, both directed and undirected. It is a greedy algorithm. Starting from the source node, you always choose an edge with least weight. When you go further down the road, and find other route with less weight, you replace the total weight accordingly.

In this implementation, the weighted graph is represented as a adjacency list. You can use existing class of WeightedGraph. A priority queue is used to sort edges by their weights. The smaller one is at the front, so that edge with smaller distance is picked first.

In Java, you use PriorityQueue class provided by Java collections. In Python, use heapq from library. In JavaScript, there is no open-box priority queue. You can implement you own PriorityQueue class.

Table of Content

Dijkstra’s algorithm

Java

import java.util.*;
public class Dijkstra<T> {
//Use priority queue, Time O(ElogV), Space O(V+E)
@SuppressWarnings({ "unchecked", "rawtypes" })
public Map<T, Integer> dijkstra(WeightedGraph<T> g, T start) {
Map<T, Integer> res = new HashMap<>(); 
PriorityQueue<Map.Entry<T, Integer>> pq =new PriorityQueue<>((a,b) -> (int)(a.getValue() - b.getValue()));           
for (T key: g.adj.keySet()) 
res.put(key, Integer.MAX_VALUE);
pq.offer(new AbstractMap.SimpleEntry(start, 0)); 
res.put(start, 0); 
while (!pq.isEmpty()) { 
T u = pq.poll().getKey(); 
for (Edge<T> x : g.adj.get(u)) {  
T v = x.connectedVetex; 
int weight = x.weight; 
if (res.get(v) > res.get(u) + weight) { 
res.put(v, res.get(u) + weight); 
pq.offer(new AbstractMap.SimpleEntry(v, res.get(v))); 
} 
} 
System.out.println(res);
} ;
return res;
}
public static void main(String args[]) { 
WeightedGraph<String> g=new WeightedGraph<>(true);	   
g.addEdge("start", "a", 1); 
g.addEdge("start", "b", 5); 
g.addEdge("a", "b", 2); 
g.addEdge("a", "d", 1); 
g.addEdge("a", "c", 2); 
g.addEdge("b", "d", 2); 
g.addEdge("c", "d", 3); 
g.addEdge("c", "e", 1); 
g.addEdge("d", "e", 2); 
Dijkstra<String> d=new Dijkstra<>();
Map<String, Integer> res= d.dijkstra(g,"start");
for(String node: res.keySet())
System.out.println(node+"-" + res.get(node));
} 
}

import java.util.*;

public class Dijkstra<T> {

//Use priority queue, Time O(ElogV), Space O(V+E)

@SuppressWarnings({ "unchecked", "rawtypes" })

public Map<T, Integer> dijkstra(WeightedGraph<T> g, T start) {

Map<T, Integer> res = new HashMap<>();

PriorityQueue<Map.Entry<T, Integer>> pq =new PriorityQueue<>((a,b) -> (int)(a.getValue() - b.getValue()));

for (T key: g.adj.keySet())

res.put(key, Integer.MAX_VALUE);

pq.offer(new AbstractMap.SimpleEntry(start, 0));

res.put(start, 0);

while (!pq.isEmpty()) {

T u = pq.poll().getKey();

for (Edge<T> x : g.adj.get(u)) {

T v = x.connectedVetex;

int weight = x.weight;

if (res.get(v) > res.get(u) + weight) {

res.put(v, res.get(u) + weight);

pq.offer(new AbstractMap.SimpleEntry(v, res.get(v)));

}

System.out.println(res);

} ;

return res;

}

public static void main(String args[]) {

WeightedGraph<String> g=new WeightedGraph<>(true);

g.addEdge("start", "a", 1);

g.addEdge("start", "b", 5);

g.addEdge("a", "b", 2);

g.addEdge("a", "d", 1);

g.addEdge("a", "c", 2);

g.addEdge("b", "d", 2);

g.addEdge("c", "d", 3);

g.addEdge("c", "e", 1);

g.addEdge("d", "e", 2);

Dijkstra<String> d=new Dijkstra<>();

Map<String, Integer> res= d.dijkstra(g,"start");

for(String node: res.keySet())

System.out.println(node+"-" + res.get(node));

}

Javascript

const GraphWeighted = require('./WeightedGraph.js') 
class PriorityQueue {
constructor() {
this.items = [];
}
//Time O(n), Space O(1)
enqueue(vertex, weight) {
var item = [vertex, weight];
var contain = false;
for (let x of this.items) {
if (x.weight> item.weight) {
this.items.splice(i, 0, item);
contain = true;
break;
}
}
if (!contain) {
this.items.push(item);
}
}
//Time O(1), Space O(1)
isEmpty() {
return this.items.length == 0;
}
//Time O(1), Space O(1)
dequeue() {
if (this.items.length == 0)
return null;
return this.items.shift();
}
}
//Use priority queue, Time O(ElogV), Space O(V+E)
function dijkstra(g, startNode) {
let res = new Map();
let pq = new PriorityQueue();
for(let node of g.adj.keys()){
res.set(node, Infinity);
}
res.set(startNode, 0);
pq.enqueue(startNode, 0);//inital vertex and weight
while (pq.isEmpty() == false) {      
var u = pq.dequeue()[0];   
for (let x of g.adj.get(u)) {  
var v = x.connectedVetex; 
var weight = x.weight; 
if (res.get(v) > res.get(u) + weight) { 
res.set(v, res.get(u) + weight); 
pq.enqueue(v, res.get(v)); 
} 
} 
}
return res;
}
var g = new GraphWeighted(true);
g.addEdge("start", "a", 1); 
g.addEdge("start", "b", 5); 
g.addEdge("a", "b", 2); 
g.addEdge("a", "d", 1); 
g.addEdge("a", "c", 2); 
g.addEdge("b", "d", 2); 
g.addEdge("c", "d", 3); 
g.addEdge("c", "e", 1); 
g.addEdge("d", "e", 2); 
res = dijkstra(g, "start");		
console.log( res)

const GraphWeighted = require('./WeightedGraph.js')

class PriorityQueue {

constructor() {

this.items = [];

}

//Time O(n), Space O(1)

enqueue(vertex, weight) {

var item = [vertex, weight];

var contain = false;

for (let x of this.items) {

if (x.weight> item.weight) {

this.items.splice(i, 0, item);

contain = true;

break;

}

if (!contain) {

this.items.push(item);

}

//Time O(1), Space O(1)

isEmpty() {

return this.items.length == 0;

}

//Time O(1), Space O(1)

dequeue() {

if (this.items.length == 0)

return null;

return this.items.shift();

}

//Use priority queue, Time O(ElogV), Space O(V+E)

function dijkstra(g, startNode) {

let res = new Map();

let pq = new PriorityQueue();

for(let node of g.adj.keys()){

res.set(node, Infinity);

}

res.set(startNode, 0);

pq.enqueue(startNode, 0);//inital vertex and weight

while (pq.isEmpty() == false) {

var u = pq.dequeue()[0];

for (let x of g.adj.get(u)) {

var v = x.connectedVetex;

var weight = x.weight;

if (res.get(v) > res.get(u) + weight) {

res.set(v, res.get(u) + weight);

pq.enqueue(v, res.get(v));

}

return res;

}

var g = new GraphWeighted(true);

g.addEdge("start", "a", 1);

g.addEdge("start", "b", 5);

g.addEdge("a", "b", 2);

g.addEdge("a", "d", 1);

g.addEdge("a", "c", 2);

g.addEdge("b", "d", 2);

g.addEdge("c", "d", 3);

g.addEdge("c", "e", 1);

g.addEdge("d", "e", 2);

res = dijkstra(g, "start");

console.log( res)

Python

import heapq
import WeightedGraph
# Use priority queue, Time O(ElogV), Space O(V+E)
def findShortestPaths(g, source):
res = {}
pq = []
for key in g.adj.keys(): 
res[key]= float('inf')
heapq.heappush(pq,  (source,0))
res[source] = 0 
while (len(pq) > 0) :
u = heapq.heappop(pq)[0]
for  x in g.adj.get(u):  
v = x.connectedVetex; 
weight = x.weight; 
if (res.get(v) > res.get(u) + weight) : 
res[v] = res.get(u) + weight
heapq.heappush(pq, (v, res.get(v)))
return res
g = WeightedGraph.WeightedGraph(False)
g.addEdge("start", "a", 1) 
g.addEdge("start", "b", 5) 
g.addEdge("a", "b", 2) 
g.addEdge("a", "d", 1) 
g.addEdge("a", "c", 2) 
g.addEdge("b", "d", 2) 
g.addEdge("c", "d", 3)
g.addEdge("c", "e", 1) 
g.addEdge("d", "e", 2)
g.printGraph()
res = findShortestPaths(g,"start")
print(res)

import heapq

import WeightedGraph

# Use priority queue, Time O(ElogV), Space O(V+E)

def findShortestPaths(g, source):

res = {}

pq = []

for key in g.adj.keys():

res[key]= float('inf')

heapq.heappush(pq, (source,0))

res[source] = 0

while (len(pq) > 0) :

u = heapq.heappop(pq)[0]

for x in g.adj.get(u):

v = x.connectedVetex;

weight = x.weight;

if (res.get(v) > res.get(u) + weight) :

res[v] = res.get(u) + weight

heapq.heappush(pq, (v, res.get(v)))

return res

g = WeightedGraph.WeightedGraph(False)

g.addEdge("start", "a", 1)

g.addEdge("start", "b", 5)

g.addEdge("a", "b", 2)

g.addEdge("a", "d", 1)

g.addEdge("a", "c", 2)

g.addEdge("b", "d", 2)

g.addEdge("c", "d", 3)

g.addEdge("c", "e", 1)

g.addEdge("d", "e", 2)

g.printGraph()

res = findShortestPaths(g,"start")

print(res)

Free download

Download Dijkstra in Java, JavaScript and Python
Shortest path and 2nd shortest path using Dijkstra

Login

Shortest path using Dijkstra’s algorithm – Graph algorithm 3