Learn how to find single source shortest path in a weighted directed acyclic graph (DAG) in linear time. We explain topological sorting by DFS, step-by-step edge relaxation, include fully-commented Python code, a hand dry-run, and clear Big-O analysis.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n Given<\/p>\n\n\n\n return an array Because the graph is a directed acyclic graph (DAG)<\/strong>, there are no cycles<\/strong>.<\/p>\n\n\n\n1. What does the problem ask?<\/h2>\n\n\n\n
\n
V<\/code> \u00ad\u2013 number of vertices labeled 0 \u2026 V-1<\/code><\/li>\n\n\n\nE<\/code> \u00ad\u2013 number of directed edges<\/li>\n\n\n\nedges[i] = [u, v, w]<\/code> \u00ad\u2013 an edge from<\/strong> u<\/code> to<\/strong> v<\/code> with positive weight w<\/code><\/li>\n<\/ul>\n\n\n\ndistance<\/code> where<\/p>\n\n\n\n\n
distance[i]<\/code> = length of the shortest path from source 0 to vertex i<\/strong><\/li>\n\n\n\ni<\/code> is unreachable, store -1<\/code>.<\/li>\n<\/ul>\n\n\n\n
\n\n\n\n2. Quick example<\/h2>\n\n\n\n