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

Question

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

1. 如果 i=j，Adj[i][j]=0
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。