Shortest path and 2nd shortest path using Dijkstra – code

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.

shortest path with dijkstra

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

JavaScript

Python

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)
Dijkstra’s algorithm in weighted Graph as adjacency list

Comments are closed