Maximize path score in DAG

Q: Maximize path score in DAG

This question evaluates proficiency in graph algorithms and optimization, focusing on reasoning about weighted directed acyclic graphs and maximizing a path score that combines node rewards and edge time costs.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Question

Given a weighted directed acyclic graph (DAG) where each node v has a score w(v) and each edge (u→v) has a time cost t(u,v), starting from node "start" (w(start)= 0) and ending at any node whose name begins with an underscore "_", find the path P that maximizes Score(P) = Σ w(v) − Σ t(u,v). Output the maximum score (and optionally the corresponding path).

Maximize path score in DAG

Overview

Question

Comments (0)