algorithm - 确定有向图中的最大路径

Question

我面临寻找有向图的所有最大路径是否满足某个条件的问题：所有最大路径（从给定的“u”顶点开始）必须“包含”一个与偶数相关联的顶点. 我的教授给出的定义是“当你不能再扩展它时，路径是最大的，即当它是无限的或以水槽结束时”这可能有点令人困惑，至少对我来说，我需要澄清开始考虑算法。例如，在给定的图中，当 u=0 时，有多少条最大路径？他们是谁？0-1-3 和 0-1-2 ？在那之后，任何人都可以给我关于我需要编写的算法的建议吗？谢谢。

标签： algorithmgraphgraph-theorydirected-graph