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$
  • $\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 '16 at 17:24
  • $\begingroup$ Longest path starting at that node $\endgroup$ – user50420 May 5 '16 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 '16 at 18:10
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, privacy policy and cookie policy

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