c - 在邻接表中找到最长的路径

Question

我有一个邻接列表，我已经为一个给定的图创建了节点和加权边。我想找出在图中找到最长路径的最佳方法。我有一个拓扑排序方法，我听说它很有用，但是我不确定如何实现它来找到最长的路径。那么，有没有一种方法可以使用拓扑排序来实现这一点，或者有没有一种更有效的方法？
下面是一个my out for the adj list的示例（括号中的值是到达箭头后面节点的成本：

Node 0 (4)->1(9)->2
Node 1 (10)->3
Node 2 (8)->3
Node 3
Node 4 (3)->8(3)->7
Node 5 (2)->8(4)->7(2)->0
Node 6 (2)->7(1)->0
Node 7 (5)->9(6)->1(4)->2
Node 8 (6)->9(5)->1
Node 9 (7)->3
Node 10 (12)->4(11)->5(1)->6

Answer 1

布赖恩已经回答了你上面的问题，但我想我可以更深入一些。
首先，正如他所指出的，这个问题只有在没有周期的情况下才容易解决。如果有周期，你会遇到无限长的路径。在这种情况下，可以将最长路径定义为没有重复节点的任何路径。不幸的是，这个问题可以证明是NP难的。因此，我们将重点讨论一个看起来需要解决的问题（因为您提到了拓扑排序）——有向无环图（DAG）中的最长路径。我们还假设有两个节点s和t是我们的开始和结束节点。除非你能对你的图表做出某些假设，否则这个问题会更难看一些。如果您理解下面的文本，并且图形中的这些假设是正确的，那么您也许可以删除s和t限制（否则，您将不得不在图形中的每一对顶点上运行它！慢……）
算法的第一步是对顶点进行拓扑排序。直觉上这是有道理的。假设您从左到右排序（即最左边的节点将没有传入的边）。从s到t的最长路径通常从左侧开始，到右侧结束。这条路也不可能朝左走。这为您提供了生成最长路径的顺序--从左开始向右移动。
下一步是按顺序从左到右移动并为每个节点定义最长路径。对于没有传入边的任何节点，该节点的最长路径为0（根据定义，这是正确的）。对于任何有输入边的节点，递归地定义该节点的最长路径，在所有进入的边上都是最大的+最长路径到达“进入”邻居（注意，这个数字可能是负的，如果，例如，所有传入的边都是负的！）。直觉上这是有道理的，但证据也很简单：
假设我们的算法声称到某个节点的最长路径是v，但实际的最长路径是一些d。选择“最小”这样的节点（我们使用拓扑排序定义的顺序）。换句话说，我们选择算法失败的“最左边”节点。这一点很重要，这样我们就可以假设我们的算法已经正确地确定了d' > d“左边”任何节点的最长路径。定义假设最长路径的长度为v，其中v是节点d' = d_1 + e的假设路径长度，边d_1到v_prev（注意草率的命名）。边缘也有重量。我们可以这样定义它，因为任何到e的路径都必须经过它的一个邻居，而这个邻居的边将变成v（因为如果不通过某个到它的边到达那里，就无法到达e）。那么e必须是v的最长路径（否则，就是矛盾。有一条较长的路径与我们选择的“最少”这样的节点相矛盾我们的算法会根据需要选择包含v的路径。
要生成实际路径，您可以确定使用了哪条边。假设你已经重建了某个顶点的路径，该顶点的路径长度最长。然后遍历所有传入的顶点，找到路径长度最长的顶点，其中v是进入d_1的边的权重。在执行算法时，还可以跟踪节点的父节点。也就是说，当您找到v_prev的最长路径时，将其父节点设置为所选的相邻节点。您可以使用简单的矛盾来说明为什么两种方法都生成最长路径。
最后是一些伪代码（抱歉，基本上是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;
}

注意，这个实现不是特别有效，但希望它是明确的！在代码/实现中，您可以用许多小的方式进行优化，这些小的方式应该是显而易见的。一般来说，如果你在内存中存储更多的东西，它会运行得更快。您构建v的方式也很关键。例如，您的节点似乎没有d_1 + e属性。但是如果没有这些，找到每个节点的传入边是一种痛苦（而且没有表现出来！）。在我看来，图形算法在概念上不同于字符串和数组上的算法，因为实现非常重要！如果您阅读关于图形算法的wiki条目，您会发现它们通常会根据不同的实现（具有不同的数据结构）给出三到四个不同的运行时。如果你在乎速度