我有一个无环有向图，它有一个开始垂直点和一个结束垂直点，中间有一些未知的顶点数一条路从起点垂直到终点垂直。已知起始垂直和结束垂直之间的任意路径上的顶点数
最佳答案
这个问题在Geekviewpoint.com上得到了解决，并给出了详细的解释它扩充了dijkstra的算法。http://www.geekviewpoint.com/java/graph/dijkstra_constrained
编辑：在每条路径之间占100个顶点。
最初你的问题是在开始和结束顶点之间有100条路径但通过修正，它实际上是路径上的100个顶点。在这种情况下，可以直接使用dfs进行优化。
当您尝试组合路径时，跟踪您看到的顶点数。如果数字达到99并且不链接开始到结束，中止该路径并尝试另一个单元，如果存在，则得到答案。需要修改的算法是用于循环检测的dfs。任何一本算法教科书都会有这样一本。因为您还需要在找到的路径中选择最佳路径，所以还应该查看http://www.geekviewpoint.com/java/graph/count_paths。
我不知道我是否应该告诉你如何做显而易见的事情，但是你会追踪你找到的类似于你在数组中找到最大元素的路径。代码并不难，你只需要结合一些小的想法：
DFS（类似于循环检测和similar to counting paths，两者重叠）
跟踪你所看到的最佳路径：一个单入口地图，其中的想法是地图，如果你发现一个较短的路径，你会不断地替换它。