Longest Weighted Path in a DAG

Preview mode. Log in to edit, run, submit, and save progress.

Medium

Description

You are given a directed acyclic graph (DAG) with weighted edges. Using a recursive CTE, enumerate all paths from every possible starting node and find the globally longest path by total edge weight. Return all paths that share the maximum total weight. Return (start_node, end_node, total_weight, path) ordered by start_node, then path. Table: Nodes

Column Name	Type	Description
node_id	INT	Primary key
node_name	VARCHAR	Node label

Table: Edges

Column Name	Type	Description
from_node	INT	Source node
to_node	INT	Destination node
weight	INT	Edge weight (non-negative)

Database Schema (Inferred)

Nodes

Column Name	Example Value
node_id	1
node_name	A

Edges

Column Name	Example Value
from_node	1
to_node	2
weight	4

Example

Nodes

node_id	node_name
1	A
2	B
3	C
4	D
5	E
6	F

Edges

from_node	to_node	weight
1	2	4
1	3	2
2	4	5
2	5	3
3	5	6
4	6	2
5	6	4

Output

start_node	end_node	total_weight	path
1	6	12	1->3->5->6

Explanation:

All paths from node 1: 1→2→4→6 (weight 11), 1→2→5→6 (weight 11), 1→3→5→6 (weight 12). The path through node 3 is longest at weight 12. The visited guard prevents cycles. Only globally maximum-weight paths are returned.

Approach hint

Start with a simple approach, explain the trade-off, then move toward a cleaner or more scalable solution.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.