Shortest path in undirected graph with unit weights
BitGoThe problem
Given a Undirected Graph of N vertices from 0 to N-1 and M edges and a 2D Integer array edges, where there is a edge from vertex edges[i][0] to vertex edges[i][1] of unit weight.
Find the shortest path from the source to all other nodes in this graph. In this problem statement, we have assumed the source vertex to be ‘0’. If a vertex is unreachable from the source node, then return -1 for that vertex.
Input: n = 9, m = 10, edges = [[0,1],[0,3],[3,4],[4,5],[5, 6],[1,2],[2,6],[6,7],[7,8],[6,8]]
Output: 0 1 2 1 2 3 3 4 4
Explanation: The above output array shows the shortest path to all the nodes from the source vertex (0), Dist[0] = 0, Dist[1] = 1 , Dist[2] = 2 , …. Dist[8] = 4.Where Dist[node] is the shortest path between src and the node. For a node, if the value of Dist[node]= -1, then we conclude that the node is unreachable from the src node.
Input: n = 8, m = 10, edges =[[1,0],[2,1],[0,3],[3,7],[3,4],[7,4],[7,6],[4,5],[4,6],[6,5]]
Output: 0 1 2 1 2 3 3 2
Explanation: The above output list shows the shortest path to all the nodes from the source vertex (0), Dist[0] = 0, Dist[1] = 1, Dist[2] = 2,.....Dist[7] = 2.
Input: n = 3, m = 1, edges = [[1,2]]
- 1<=n,m<=104
- 0<=edges[i][j]<=n-1
cpp
class Solution {
public:
vector<int> shortestPath(vector<vector<int>>& edges, int N,int M){
}
};java
class Solution {
public int[] shortestPath(int[][] edges, int N, int M) {
}
}python
class Solution:
def shortestPath(self, edges, N, M):javascript
class Solution {
shortestPath(edges, N, M) {
}
}csharp
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public List<int> shortestPath(List<List<int>> edges, int N, int M)
{
}
}go
func shortestPath(edges [][]int, N int, M int) []int {
}Stuck? Show a way to structure it+
- 01Build an undirected adjacency list
- 02Initialize all distances as unvisited
- 03Enqueue the source and mark it immediately
- 04Visit each neighbor once and assign distance plus one
Reference answer
Then expect these follow-ups
How do you return the actual shortest path?
Tests: implementation extension
What changes when edges have weights?
Tests: constraint adaptation
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question