0
$\begingroup$

I'm interested in implementing an algorithm detailed on this Wiki page for finding the longest path of a DAG.

The second part of the algorithm says the length of the longest path of a node with no outgoing edges should be zero, but my programming professor says this node should return 1 as its longest path length. (Perhaps he says this assuming each node's length is set to 0 and a recursive function that visits each node will add 1 to whichever child has the longest path.)

I think that if someone can answer the question: what is the length of the longest path of a DAG containing a single node, then I will have an answer to my question. Though, I'm not sure if a single-node graph constitutes a DAG.

As you can probably tell, I'm new to graphs, so any guidance is appreciated.

$\endgroup$
3
  • $\begingroup$ What do you mean by "longest path of a node"? Longest path starting at that node? ending at that node? Something else? $\endgroup$
    – D.W.
    May 5, 2016 at 17:24
  • $\begingroup$ Longest path starting at that node $\endgroup$
    – user50420
    May 5, 2016 at 17:29
  • $\begingroup$ Please edit your question accordingly. Comments exist only to help you improve your question; all relevant information should be in the question. Thank you! $\endgroup$
    – D.W.
    May 5, 2016 at 18:10

1 Answer 1

1
$\begingroup$

You have not misunderstood anything, there is simply a discrepancy of notation: sometimes the length of a path is measured as its number of edges, sometimes as its number of nodes, depending on context. In your implementation, it doesn't matter which convention you use, as long as you are consistent throughout your algorithm. Then if you use the second convention and your algorithm returns $3$ for a particular vertex, it means the longest path to that vertex has three nodes: $abv$. If you use the first convention (which is what this Wikipedia article uses, but not your professor), the algorithm should return $2$, because the longest path has two edges.

If this is an assignment, and your professor uses the convention that paths are measured by their vertices, and says that you should too, then you should too.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.