布莱恩已经在上面回答了你的问题，但我想我可以更深入地讨论。
首先，正如他所指出的，这个问题只有在没有循环的情况下才容易解决。如果存在循环，您会遇到路径无限长的情况。在这种情况下，您可以将最长路径定义为没有重复节点的任何路径。不幸的是，这个问题可以证明是 NP-Hard。因此，相反，我们将关注您似乎实际需要解决的问题（因为您提到了拓扑排序）——有向无环图 (DAG) 中的最长路径。我们还将假设我们有两个节点s，t即开始节点和结束节点。除非您可以对图表做出某些假设，否则问题会更难看。如果您理解下面的文字，并且图表中的此类假设是正确的，那么也许您可以删除s和t限制（否则，您必须在图中的每一对顶点上运行它！慢...）
算法的第一步是对顶点进行拓扑排序。直觉上这是有道理的。假设您从左到右对它们进行排序（即最左边的节点将没有传入边）。s从到的最长路径t通常从左侧开始并在右侧结束。这条路也不可能向左走。这为您提供了一个顺序排序来生成最长的路径——从左侧开始并向右移动。
下一步是从左到右依次为每个节点定义最长的路径。对于没有传入边的任何节点，到该节点的最长路径为 0（根据定义，这是真的）。对于任何具有传入边的节点，递归地将到该节点的最长路径定义为所有传入边上的最大值 + 到达“传入”邻居的最长路径（请注意，这个数字可能是负数，例如，如果所有的传入边缘是负的！）。直觉上这是有道理的，但证明也是微不足道的：
假设我们的算法声称到某个节点的最长路径v是，d但实际最长的路径是 some d' > d。选择“最少”这样的节点v（我们使用拓扑排序定义的排序。换句话说，我们选择算法失败的“最左边”节点。这很重要，因此我们可以假设我们的算法有正确确定了v) 左侧任何节点的最长路径。将假设的最长路径的长度定义为d' = d_1 + e其中d_1是假设路径的长度，直到v_prev具有边缘e到的节点v（注意草率的命名。边缘e也有 weight e）。我们可以这样定义它，因为任何通往v必须通过它的一个有边缘的邻居（因为如果不通过一些边缘到达那里，v你就无法到达）。v然后d_1必须是最长的路径v_prev（否则，矛盾。有一条更长的路径与我们选择v的“最小”此类节点相矛盾！）并且我们的算法将d_1 + e根据需要选择包含的路径。
要生成实际路径，您可以确定使用了哪条边。假设您已经将路径重建到某个v具有最长路径长度的顶点d。然后遍历所有传入的顶点，找到路径长度最长的顶点，d' = d - e其中e边的权重是v。您也可以在通过算法时跟踪节点的父节点。也就是说，当您找到 的最长路径时v，将其父节点设置为选择的任何相邻节点。您可以使用简单的矛盾来说明为什么任何一种方法都会生成最长的路径。
最后是一些伪代码（抱歉，它基本上是用 C# 编写的。在没有自定义类的情况下用 C 编写代码会更麻烦，而且我有一段时间没有编写 C 代码了）。
public List<Nodes> FindLongestPath(Graph graph, Node start, Node end)
{
var longestPathLengths = Dictionary<Node, int>;
var orderedNodes = graph.Nodes.TopologicallySort();
// Remove any nodes that are topologically less than start.
// They cannot be in a path from start to end by definition
while (orderedNodes.Pop() != start);
// Push it back onto the top of the stack
orderedNodes.Push(start);
// Do algorithm until we process the end node
while (1)
{
var node = orderedNodes.Pop();
if (node.IncomingEdges.Count() == 0)
{
longestPathLengths.Add(node, 0);
}
else
{
var longestPathLength = Int.Min;
foreach (var incomingEdge in node.IncomingEdges)
{
var currPathLength = longestPaths[incomingEdge.Parent] +
incomingEdge.Weight);
if (currPathlength > longestPathLength)
{
longestPath = currPathLength;
}
}
longestPathLengths.Add(node, longestPath);
}
if (node == end)
{
break;
}
}
// Reconstruct path. Go backwards until we hit start
var node = end;
var longestPath = new List<Node>();
while (node != start)
{
foreach (var incomingEdge in node.IncomingEdges)
{
if (longestPathLengths[incomingEdge.Parent] ==
longestPathLengths[node] - incomingEdge.Weight)
{
longestPath.Prepend(incomingEdge.Parent);
node = incomingEdge.Parent;
break;
}
}
}
return longestPath;
}
请注意，此实现并不是特别有效，但希望它很清楚！您可以通过许多小方式进行优化，这些方式在您考虑代码/实现时应该是显而易见的。一般来说，如果你在内存中存储更多的东西，它会运行得更快。你的结构方式Graph也很关键。例如，您似乎没有IncomingEdges节点的属性。但是没有它，为每个节点找到传入的边是一件很痛苦的事情（而且不是高性能的！）。在我看来，图算法在概念上不同于字符串和数组算法，因为实现非常重要！如果您阅读有关图形算法的 wiki 条目，您会发现它们通常会根据不同的实现（具有不同的数据结构）提供三到四种不同的运行时。如果您关心速度，请记住这一点