Shortest path and 2nd shortest path using dijkstra

Dijkstra’s algorithm is an algorithm to find the shortest paths between vertices in a graph. It uses greedy technique by picking the un-visited vertex with the lowest distance. When all vertices have been evaluated, the result is the shortest path. This post provides code to find shortest path and second shortest path by using Dijkstra algorithm.

Find 2nd shortest path is a Find kth problem. It can be achieved by using K_shortest_path_routing or Yen’s_algorithm. However I introduce a simple approach. The steps are: first find the shortest path using dijkstra. Second, remove each edge in the shortest path. Now find the shortest path again. Finally compare and return the shortest path among them as the second shortest path from source to destination.

In the following implementation, the graph is undirected and represented as a matrix.

Amazon Interview Question:
You are given a graph and an algorithm that can find the shortest
the path between any two nodes
Now you have to find the second shortest path between the same two nodes.

Java

import java.util.*;
public class ShortestPathAnd2ndShortestDijkstras {
	static final int NO_PARENT = -1;	
	static Set<Integer> path = new LinkedHashSet<>(); //nodes in the shortest path
	static Set<Integer> allDists = new TreeSet<>(); //list of shortest distance, sorted
	
	//use Dijkstra’s Shortest Path Algorithm, Time O(n^2)  n is number of nodes
    //auxillary Space O(n)
    static void shortestPath(int[][] adjacencyMatrix,  int src, int dest) { 
        int n = adjacencyMatrix[0].length; 
        int[] shortest = new int[n]; 
        boolean[] visited = new boolean[n];
        int[] parents = new int[n]; 
        for (int v = 0; v < n; v++)  { 
            shortest[v] = Integer.MAX_VALUE; 
            visited[v] = false; 
        } 
        shortest[src] = 0; 
        parents[src] = NO_PARENT; 
        for (int i = 1; i < n; i++)  { 
            int pre = -1; 
            int min = Integer.MAX_VALUE; 
            for (int v = 0;  v < n;  v++) { 
                if (!visited[v] && shortest[v] < min) { 
                    pre = v; 
                    min = shortest[v]; 
                } 
            } 
            if(pre==-1)
            	return;
            visited[pre] = true; 
            for (int v = 0; v < n; v++)  { 
                int dist = adjacencyMatrix[pre][v];                  
                if (dist > 0 && ((min + dist) < shortest[v]))  { 
                    parents[v] = pre; 
                    shortest[v] = min + dist; 
                } 
            } 
        }  
        allDists.add(shortest[dest]);
        addPath(dest, parents); 
    } 
    
    //utility func to add nodes in the path recursively
    //Time O(n), Space O(n)
    static void addPath(int i,int[] parents)  { 	
        if (i == NO_PARENT)        	
            return;   	
        addPath(parents[i], parents);             
        path.add(i);
    } 
    
    //get 2nd shortest by removing each edge in shortest and compare  
    //Time O(n^3), Space O(n)
    static void find2ndShortest(int[][] adjacencyMatrix,int src, int dest) {    	
    	 int preV = -1, preS = -1, preD = -1; //store previous vertex's data
         List<Integer> list = new ArrayList<Integer>(path);        
         for (int i = 0; i < list.size()-1 ; i++) {
        	//get source and destination for each path in shortest path
         	int s = list.get(i);
         	int d = list.get(i + 1);
         	if (preV != -1) {//resume the previous path 
         		adjacencyMatrix[preS][preD] = preV;
         		adjacencyMatrix[preD][preS] = preV;
         	}
         	//record the previous data for recovery
         	preV = adjacencyMatrix[s][d];
         	preS = s;
         	preD = d;
         	//remove this path
 	        adjacencyMatrix[s][d] = 0;
 	        adjacencyMatrix[d][s] = 0;
 	        //re-calculate
 	        shortestPath(adjacencyMatrix, src , dest);
         }
    }
    public static void main(String[] args) { 
		/*
		 *     0
		 *  10/ \3
		 *   /   \
		 *  1--1--4
		 * 5|  8/ |2
		 *  | /   |
		 *  2--7--3
		 */  	
   	
        int[][] adjacencyMatrix = new int[][] {
            { 0,10, 0, 0, 3 },
            { 10, 0, 5, 0, 1 },
            { 0, 5, 0, 7, 8 },
            { 0, 0, 7, 0, 2 },
            { 3, 1, 8, 2, 0 }
        };
        
        int src = 2, dest = 4;
        shortestPath(adjacencyMatrix,src,dest); 
        find2ndShortest(adjacencyMatrix,src,dest); 
        
        List<Integer> list = new ArrayList<Integer>(allDists); 
        System.out.println("Shortest:" + list.get(0));
        System.out.println("2nd shortest:" + list.get(1));            
    } 
}

100

101

102

103

104

import java.util.*;

public class ShortestPathAnd2ndShortestDijkstras {

static final int NO_PARENT = -1;

static Set<Integer> path = new LinkedHashSet<>(); //nodes in the shortest path

static Set<Integer> allDists = new TreeSet<>(); //list of shortest distance, sorted

//use Dijkstra’s Shortest Path Algorithm, Time O(n^2) n is number of nodes

//auxillary Space O(n)

static void shortestPath(int[][] adjacencyMatrix, int src, int dest) {

int n = adjacencyMatrix[0].length;

int[] shortest = new int[n];

boolean[] visited = new boolean[n];

int[] parents = new int[n];

for (int v = 0; v < n; v++) {

shortest[v] = Integer.MAX_VALUE;

visited[v] = false;

}

shortest[src] = 0;

parents[src] = NO_PARENT;

for (int i = 1; i < n; i++) {

int pre = -1;

int min = Integer.MAX_VALUE;

for (int v = 0; v < n; v++) {

if (!visited[v] && shortest[v] < min) {

pre = v;

min = shortest[v];

}

if(pre==-1)

return;

visited[pre] = true;

for (int v = 0; v < n; v++) {

int dist = adjacencyMatrix[pre][v];

if (dist > 0 && ((min + dist) < shortest[v])) {

parents[v] = pre;

shortest[v] = min + dist;

}

allDists.add(shortest[dest]);

addPath(dest, parents);

}

//utility func to add nodes in the path recursively

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

static void addPath(int i,int[] parents) {

if (i == NO_PARENT)

return;

addPath(parents[i], parents);

path.add(i);

}

//get 2nd shortest by removing each edge in shortest and compare

//Time O(n^3), Space O(n)

static void find2ndShortest(int[][] adjacencyMatrix,int src, int dest) {

int preV = -1, preS = -1, preD = -1; //store previous vertex's data

List<Integer> list = new ArrayList<Integer>(path);

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

//get source and destination for each path in shortest path

int s = list.get(i);

int d = list.get(i + 1);

if (preV != -1) {//resume the previous path

adjacencyMatrix[preS][preD] = preV;

adjacencyMatrix[preD][preS] = preV;

}

//record the previous data for recovery

preV = adjacencyMatrix[s][d];

preS = s;

preD = d;

//remove this path

adjacencyMatrix[s][d] = 0;

adjacencyMatrix[d][s] = 0;

//re-calculate

shortestPath(adjacencyMatrix, src , dest);

}

public static void main(String[] args) {

* 0

* 10/ \3

* / \

* 1--1--4

* 5| 8/ |2

* | / |

* 2--7--3

int[][] adjacencyMatrix = new int[][] {

{ 0,10, 0, 0, 3 },

{ 10, 0, 5, 0, 1 },

{ 0, 5, 0, 7, 8 },

{ 0, 0, 7, 0, 2 },

{ 3, 1, 8, 2, 0 }

};

int src = 2, dest = 4;

shortestPath(adjacencyMatrix,src,dest);

find2ndShortest(adjacencyMatrix,src,dest);

List<Integer> list = new ArrayList<Integer>(allDists);

System.out.println("Shortest:" + list.get(0));

System.out.println("2nd shortest:" + list.get(1));

}

JavaScript

class ShortestPathAnd2ndShortestDijkstras {
    NO_PARENT = -1;	
    path = new Set(); //nodes in the shortest path
    allDists = new Set(); //list of shortest distance
    //use Dijkstra’s Shortest Path Algorithm, Time O(n^2)  n is number of nodes
    //auxillary Space O(n)
    shortestPath(adjacencyMatrix,  src, dest) { 
        var n = adjacencyMatrix[0].length; 
        var shortest = {}; 
        var visited = {};
        var parents = {}; 
        for (let v = 0; v < n; v++)  { 
            shortest[v] =  Number.MAX_VALUE; 
            visited[v] = false; 
        } 
        shortest[src] = 0; 
        parents[src] = this.NO_PARENT; 
        for (let i = 1; i < n; i++)  { 
            let pre = -1; 
            let min =  Number.MAX_VALUE; 
            for (let v = 0;  v < n;  v++) { 
                if (!visited[v] && shortest[v] < min) { 
                    pre = v; 
                    min = shortest[v]; 
                } 
            } 
            if(pre==-1)
                return;
            visited[pre] = true; 
            for (let v = 0; v < n; v++)  { 
                let dist = adjacencyMatrix[pre][v];                  
                if (dist > 0 && ((min + dist) < shortest[v]))  { 
                    parents[v] = pre; 
                    shortest[v] = min + dist; 
                } 
            } 
        }  
        this.allDists.add(shortest[dest]);
        this.addPath(dest, parents); 
    } 
    //utility func to add nodes in the path recursively
    //Time O(n), Space O(n)
    addPath(i, parents)  { 	
        if (i == this.NO_PARENT)        	
            return;   	
        this.addPath(parents[i], parents);             
        this.path.add(i);
    } 
    //get 2nd shortest by removing each edge in shortest and compare  
    //Time O(n^3), Space O(n)
    find2ndShortest(adjacencyMatrix, src, dest) {    	
        var preV = -1, preS = -1, preD = -1; //store previous vertex's data
        var list = Array.from(this.path);       
        for (let i = 0; i < list.length-1 ; i++) {
            //get source and destination for each path in shortest path
            let s = list[i];
            let d = list[i + 1];
            if (preV != -1) {//resume the previous path 
                adjacencyMatrix[preS][preD] = preV;
                adjacencyMatrix[preD][preS] = preV;
            }
            //record the previous data for recovery
            preV = adjacencyMatrix[s][d];
            preS = s;
            preD = d;
            //remove this path
            adjacencyMatrix[s][d] = 0;
            adjacencyMatrix[d][s] = 0;
            //re-calculate
            this.shortestPath(adjacencyMatrix, src, dest);
        }
    }
}
		/*
		 *     0
		 *  10/ \3
		 *   /   \
		 *  1--1--4
		 * 5|  8/ |2
		 *  | /   |
		 *  2--7--3
		 */ 
const adjacencyMatrix = [
    [ 0,10, 0, 0, 3 ],
    [ 10, 0, 5, 0, 1 ],
    [ 0, 5, 0, 7, 8 ],
    [ 0, 0, 7, 0, 2 ],
    [ 3, 1, 8, 2, 0 ]
];
let src = 2, dest = 4;
myObj = new ShortestPathAnd2ndShortestDijkstras();
myObj.shortestPath(adjacencyMatrix, src, dest); 
myObj.find2ndShortest(adjacencyMatrix, src, dest); 
let list = Array.from(myObj.allDists); 
console.log("Shortest distance: " + list[0]);
console.log("2nd shortest distance: " + list[1]);

class ShortestPathAnd2ndShortestDijkstras {

NO_PARENT = -1;

path = new Set(); //nodes in the shortest path

allDists = new Set(); //list of shortest distance

//use Dijkstra’s Shortest Path Algorithm, Time O(n^2) n is number of nodes

//auxillary Space O(n)

shortestPath(adjacencyMatrix, src, dest) {

var n = adjacencyMatrix[0].length;

var shortest = {};

var visited = {};

var parents = {};

for (let v = 0; v < n; v++) {

shortest[v] = Number.MAX_VALUE;

visited[v] = false;

}

shortest[src] = 0;

parents[src] = this.NO_PARENT;

for (let i = 1; i < n; i++) {

let pre = -1;

let min = Number.MAX_VALUE;

for (let v = 0; v < n; v++) {

if (!visited[v] && shortest[v] < min) {

pre = v;

min = shortest[v];

}

if(pre==-1)

return;

visited[pre] = true;

for (let v = 0; v < n; v++) {

let dist = adjacencyMatrix[pre][v];

if (dist > 0 && ((min + dist) < shortest[v])) {

parents[v] = pre;

shortest[v] = min + dist;

}

this.allDists.add(shortest[dest]);

this.addPath(dest, parents);

}

//utility func to add nodes in the path recursively

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

addPath(i, parents) {

if (i == this.NO_PARENT)

return;

this.addPath(parents[i], parents);

this.path.add(i);

}

//get 2nd shortest by removing each edge in shortest and compare

//Time O(n^3), Space O(n)

find2ndShortest(adjacencyMatrix, src, dest) {

var preV = -1, preS = -1, preD = -1; //store previous vertex's data

var list = Array.from(this.path);

for (let i = 0; i < list.length-1 ; i++) {

//get source and destination for each path in shortest path

let s = list[i];

let d = list[i + 1];

if (preV != -1) {//resume the previous path

adjacencyMatrix[preS][preD] = preV;

adjacencyMatrix[preD][preS] = preV;

}

//record the previous data for recovery

preV = adjacencyMatrix[s][d];

preS = s;

preD = d;

//remove this path

adjacencyMatrix[s][d] = 0;

adjacencyMatrix[d][s] = 0;

//re-calculate

this.shortestPath(adjacencyMatrix, src, dest);

}

* 0

* 10/ \3

* / \

* 1--1--4

* 5| 8/ |2

* | / |

* 2--7--3

const adjacencyMatrix = [

[ 0,10, 0, 0, 3 ],

[ 10, 0, 5, 0, 1 ],

[ 0, 5, 0, 7, 8 ],

[ 0, 0, 7, 0, 2 ],

[ 3, 1, 8, 2, 0 ]

];

let src = 2, dest = 4;

myObj = new ShortestPathAnd2ndShortestDijkstras();

myObj.shortestPath(adjacencyMatrix, src, dest);

myObj.find2ndShortest(adjacencyMatrix, src, dest);

let list = Array.from(myObj.allDists);

console.log("Shortest distance: " + list[0]);

console.log("2nd shortest distance: " + list[1]);

Python

import sys
class ShortestPathAnd2ndShortestDijkstras:
    def __init__(self) : 
        self.NO_PARENT = -1	
        self.path = [] #nodes in the shortest path
        self.allDists = [] #list of shortest distance, keep insertion order
    # use Dijkstra’s Shortest Path Algorithm, Time O(n^2)  n is number of nodes
    #auxillary Space O(n)
    def shortestPath(self, adjacencyMatrix, src, dest) : 
        n = len(adjacencyMatrix[0]) 
        shortest = {}
        visited = {}
        parents = {}
        for v in range(0, n, 1)  :
            shortest[v] =  sys.maxsize; 
            visited[v] = False
        shortest[src] = 0; 
        parents[src] = self.NO_PARENT; 
        for i in range(1, n, 1) : 
            pre = -1; 
            min =  sys.maxsize; 
            for v in range(0, n, 1) : 
                if visited[v]==False and shortest[v] < min : 
                    pre = v; 
                    min = shortest[v]; 
            if pre == -1:
                return
            visited[pre] = True; 
            for v in range(0, n, 1)  : 
                dist = adjacencyMatrix[pre][v];                  
                if dist > 0 and ((min + dist) < shortest[v]) :   
                    parents[v] = pre
                    shortest[v] = min + dist 
        self.allDists.append(shortest[dest])
        self.addPath(dest, parents); 
    
    #utility func to add nodes in the path recursively
    #Time O(n), Space O(n)
    def addPath(self, i, parents) : 	
        if (i == self.NO_PARENT) :
            return  	
        self.addPath(parents[i], parents)             
        self.path.append(i) 
    #get 2nd shortest by removing each edge in shortest and compare  
    #Time O(n^3), Space O(n)
    def find2ndShortest(self, adjacencyMatrix, src, dest) : 
        #store previous vertex's data  	
        preV = -1
        preS = -1 
        preD = -1 
        mylist = list(self.path)   
        for i in range(0, len(mylist)-1, 1) :
            #get source and destination for each path in shortest path
            s = mylist[i]
            d = mylist[i + 1]
            #resume the previous path 
            if (preV != -1) :
                adjacencyMatrix[preS][preD] = preV
                adjacencyMatrix[preD][preS] = preV       
            #record the previous data for recovery
            preV = adjacencyMatrix[s][d]
            preS = s
            preD = d
            #remove this path
            adjacencyMatrix[s][d] = 0
            adjacencyMatrix[d][s] = 0
            #re-calculate
            self.shortestPath(adjacencyMatrix, src, dest)
    
		# 
		#      0
		#   10/ \3
		#    /   \
		#   1--1--4
		#  5|  8/ |2
		#   | /   |
		#   2--7--3
		#   
adjacencyMatrix = [
            [ 0,10, 0, 0, 3 ],
            [ 10, 0, 5, 0, 1 ],
            [ 0, 5, 0, 7, 8 ],
            [ 0, 0, 7, 0, 2 ],
            [ 3, 1, 8, 2, 0 ]
]
src = 2
dest = 4
myobj = ShortestPathAnd2ndShortestDijkstras()
myobj.shortestPath(adjacencyMatrix, src, dest); 
myobj.find2ndShortest(adjacencyMatrix, src, dest); 
print("Shortest distance: " + str(myobj.allDists[0]))
print("2nd shortest distance: " + str(myobj.allDists[1]))

import sys

class ShortestPathAnd2ndShortestDijkstras:

def __init__(self) :

self.NO_PARENT = -1

self.path = [] #nodes in the shortest path

self.allDists = [] #list of shortest distance, keep insertion order

# use Dijkstra’s Shortest Path Algorithm, Time O(n^2) n is number of nodes

#auxillary Space O(n)

def shortestPath(self, adjacencyMatrix, src, dest) :

n = len(adjacencyMatrix[0])

shortest = {}

visited = {}

parents = {}

for v in range(0, n, 1) :

shortest[v] = sys.maxsize;

visited[v] = False

shortest[src] = 0;

parents[src] = self.NO_PARENT;

for i in range(1, n, 1) :

pre = -1;

min = sys.maxsize;

for v in range(0, n, 1) :

if visited[v]==False and shortest[v] < min :

pre = v;

min = shortest[v];

if pre == -1:

return

visited[pre] = True;

for v in range(0, n, 1) :

dist = adjacencyMatrix[pre][v];

if dist > 0 and ((min + dist) < shortest[v]) :

parents[v] = pre

shortest[v] = min + dist

self.allDists.append(shortest[dest])

self.addPath(dest, parents);

#utility func to add nodes in the path recursively

#Time O(n), Space O(n)

def addPath(self, i, parents) :

if (i == self.NO_PARENT) :

return

self.addPath(parents[i], parents)

self.path.append(i)

#get 2nd shortest by removing each edge in shortest and compare

#Time O(n^3), Space O(n)

def find2ndShortest(self, adjacencyMatrix, src, dest) :

#store previous vertex's data

preV = -1

preS = -1

preD = -1

mylist = list(self.path)

for i in range(0, len(mylist)-1, 1) :

#get source and destination for each path in shortest path

s = mylist[i]

d = mylist[i + 1]

#resume the previous path

if (preV != -1) :

adjacencyMatrix[preS][preD] = preV

adjacencyMatrix[preD][preS] = preV

#record the previous data for recovery

preV = adjacencyMatrix[s][d]

preS = s

preD = d

#remove this path

adjacencyMatrix[s][d] = 0

adjacencyMatrix[d][s] = 0

#re-calculate

self.shortestPath(adjacencyMatrix, src, dest)

# 0

# 10/ \3

# / \

# 1--1--4

# 5| 8/ |2

# | / |

# 2--7--3

adjacencyMatrix = [

[ 0,10, 0, 0, 3 ],

[ 10, 0, 5, 0, 1 ],

[ 0, 5, 0, 7, 8 ],

[ 0, 0, 7, 0, 2 ],

[ 3, 1, 8, 2, 0 ]

]

src = 2

dest = 4

myobj = ShortestPathAnd2ndShortestDijkstras()

myobj.shortestPath(adjacencyMatrix, src, dest);

myobj.find2ndShortest(adjacencyMatrix, src, dest);

print("Shortest distance: " + str(myobj.allDists[0]))

print("2nd shortest distance: " + str(myobj.allDists[1]))

Output:
Shortest distance: 6
2nd shortest distance: 8

O Notation:
Shortest path: Time complexity: O(n^2), Space complexity: O(n)
Second shortest path: Time complexity: O(n^3), Space complexity: O(n)

Download ShortestPathAnd2ndShortestDijkstras.java
Download ShortestPathAnd2ndShortestDijkstras.js
Download ShortestPathAnd2ndShortestDijkstras.py
Find shortest and 2nd shortest distance in graph (YouTube)

Shortest path and 2nd shortest path using Dijkstra – code

Java

JavaScript

Python

Related

Recent Posts

Categories

La Vivien’s Illustrated Data structures (Java) book

Grokking Data Structures

Big O Notation Cheat sheet

Java coding interview book

Data structures Python book

Data structures JavaScript book

Shortest path and 2nd shortest path using Dijkstra – code

Java

JavaScript

Python

Share this:

Related

Recent Posts

Categories

La Vivien’s Illustrated Data structures (Java) book

Grokking Data Structures

Big O Notation Cheat sheet

Java coding interview book

Data structures Python book

Data structures JavaScript book