What is Dijkstra’s algorithm? 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.
Find 2nd shortest path is a Find kth problem. It can be achieved by using K_shortest_path_routing or Yen’s_algorithm. Here I introduce a simple approach to find shortest path and 2nd shortest path using Dijkstra. 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 un-directed, and represented as matrix.
Amazon Interview Question:
You are given a graph and an algorithm that can find the shortest
path between any two nodes
Now you have to find the second shortest path between same two nodes.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
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)
Java Coding Interview Pocket Book (2nd Edition)
