Shortest Path in DAG
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Find the shortest path from a source to all nodes in a Directed Acyclic Graph (DAG) with weighted edges., Directed Acyclic Graph, Graph, Adjacency List, Topological Sorting, Depth-First Search, Stack, Distance Calculation, Time Complexity, Space Complexity, graph representation, topological sort, graph algorithms, graph traversal, shortest path algorithms, graph properties, time complexity analysis, Shortest Path (Dijkstra's Algorithm), Graph Representation.
Given a Directed Acyclic Graph (DAG) with N vertices and M weighted edges, find the shortest path from a specified source vertex (assumed to be 0) to all other vertices. If a vertex is unreachable from the source, its distance should be considered 1. Input Format: The first line of input implicitly defines N and M through the number of nodes and edges provided in the subsequent lines. Each of the M lines following describe an edge: u, v, and wt. This denotes a directed edge from vertex u to vertex v with an associated weight wt. Output Format: Output N space separated integers, where the i th integer represents the shortest distance from the source vertex 0 to vertex i. If a vertex is unreachable, output 1 for that vertex. Constraints: Implicitly, vertices are 0 indexed. The graph is guaranteed to be a Directed Acyclic Graph (DAG). Example 1: Input: N = 6, M = 7 Edges = [[0,1,2],[0,4,1],[4,5,4],[4,2,2],[1,2,3],[2,3,6],[5,3,1]] Output: 0 2 3 6 1 5 Explanation: Dist[0] = 0 Dist[1] = 2 Dist[2] = 3 Dist[3] = 6 Dist[4] = 1 Dist[5] = 5 Example 2: Input: N = 7, M = 8 Edges = [[0,4,2],[0,5,3],[5,4,1],[4,6,3],[4,2,1],[6,1,2],[2,3,3],[1,3,1]] Output: 0 7 3 6 2 3 5 Explanation: Dist[0] = 0 Dist[1] = 7 Dist[2] = 3 Dist[3] = 6 Dist[4] = 2 Dist[5] = 3 Dist[6] = 5