# Longest path of a DAG containing a single node?

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.

• What do you mean by "longest path of a node"? Longest path starting at that node? ending at that node? Something else?
– D.W.
May 5 '16 at 17:24
• Longest path starting at that node May 5 '16 at 17:29
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.