Longest Weighted Path in a DAG
Preview mode. Log in to edit, run, submit, and save progress.
Longest Weighted Path in a DAG
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) |
Examples
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.