A short post of Dijkstra's algorithm

Dijkstra’s algorithm is an algorithm to find the shortest paths from the 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 the least weight. When you go further down the road, and find other routes with less weight, you replace the total weight accordingly.

In this implementation, the weighted graph is represented as an adjacency list. You can use the 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 a smaller distance is picked first.

In Java, you use the PriorityQueue class provided by Java collections. In Python, use heapq from the library. In JavaScript, there is no open-box priority queue. You can implement your 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

A short post of Dijkstra’s algorithm