algorithm - DAG 中所有对之间的最长路径

Question

我试图在非循环有向图中找到所有节点对之间的最长路径。我的问题是，如果我在邻接矩阵中设置以下初始条件，Floyyd Warshall 会给出正确答案吗？

1. Adj[i][j]=0 如果 i=j
2. Adj[i][j]=-1*INF if i!=j 并且节点 i 和 j 之间没有边
3. Adj[i][j]=w[i][j] 否则，其中w[i][j]是节点i和j之间边的权重

边的权重可以是正的也可以是负的。

Answer 1

是的，Floyd Warshall 可以为您的问题给出正确答案，可以像使用 Floyd Warshall 找到图中所有对之间的最短路径一样证明。或者您可以将每条边与 (-1) 相乘，并解决您的问题，例如找到所有对之间的最短路径，然后将您的结果与 (-1) 相乘。

但是你可以对图进行拓扑排序，然后用动态规划来计算，复杂度是max(|E|,|V|)而不是FW的|V|^3。