Is the longest path in a (weighted) DAG always from a source to a sink? This seems correct to me by intuition, but I'm not 100% confident. Like, for example, if I had an array in which each index represented a node in topological order, and stored the length of the longest path with that node as its endpoint in the graph at that index, would the longest path in the graph always be stored in the last index?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ You need to draw some more examples. Try adding nodes and vertices to contradict your claim; you'll either find a counter-example, or learn something about how to prove it. $\endgroup$– RaphaelCommented Nov 8, 2017 at 6:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
First, notice that your topological sort comment isn't quite right, because other nodes can be sinks than the last node in a topological sort.
To your original question: Consider some path in a DAG that is not from a source to a sink. Can you show that this path can be made longer? (This implies that the longest path must be from a source to a sink.)
For example, if the path does not start at a source, then it has at least one incoming edge... (make sure you use the fact that the graph is a DAG).
