Shortest Path in Undirected Graph with Unit Weights
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Finding the shortest path from a source to all nodes in an undirected graph with unit weights, Graph, Undirected Graph, Adjacency List, Graph Traversal, Breadth-First Search, Queue, Distance Calculation, Time Complexity, Space Complexity, Arrays, graph representation, graph algorithms, visited tracking, graph traversal, queue, bfs, Shortest Path Utilities, Directed Acyclic Graph (DAG).
Shortest Path in an Undirected Graph with Unit Weights Given an undirected graph with unit weight edges, find the shortest path from a specified source node to all other nodes in the graph. If a node is unreachable from the source, its shortest path distance should be reported as 1. Input Specification: n: An integer representing the number of vertices in the graph. m: An integer representing the number of edges in the graph. edges: A list of lists, where each inner list [u, v] represents an undirected edge between node u and node v. src: An integer representing the source vertex. Output Specification: A list of integers Dist, where Dist[i] is the shortest distance from the src node to node i. If node i is unreachable from src, Dist[i] should be 1. Sample Test Cases: Example 1: Input: Output: Explanation: The output array shows the shortest path to all the nodes from the source vertex (0). For example, Dist[0] = 0, Dist[1] = 1, Dist[2] = 2, Dist[8] = 4. If Dist[node] = 1, it indicates the node is unreachable from the source node. Example 2: Input: Output: Explanation: The output list shows the shortest path to all the nodes from the source vertex (0). For example, Dist[0] = 0, Dist[1] = 1, Dist[2] = 2, Dist[7] = 2.