java - 具有邻接矩阵的未加权图上的最长路径

Question

我首先查看了其他问题，并没有找到任何正确的答案。假设有一个二维数组，其中保存了两个节点，并且输入一个整数，其中包含所有节点的总数。现在的任务是在 Java 中找到有向无环图中的最长路径。

我首先有运行 Bfs 的想法，例如：

long longestPath(long length, long Array[][])
{
int[] max = new int;
if( !visited(V)
    {dfs(v); maximum[] = max[dfs.distance};}
}

那时我停在这里，因为我认为 dfs 只适用于树。然后我有了使用拓扑排序的想法。我确实不知道如何用二维数组来实现它。有人有想法吗？

标签： javaalgorithmdata-structures

Answer 1

是的，你必须做拓扑排序。DAG中的最长路径可以通过巧妙的变换来找到，即使用当前边权重的负值。在新转换的图中，您可以找到最短路径。而这个值的负数就是最长的路径。

为了在 DAG 中找到最短路径，您首先进行顶级排序，然后按该顺序更新

// do this for all the valid adjacent edges according to your matrix
// u is the current vertex you are processing in the topological order
if(cost[u] + w < cost[v]) // assume the edge is from u to v 
{
    cost[v] = cost[u] + w;
}