Longest path between all pairs in a DAG

Question

I was trying to find the longest path between all pair of nodes in an acyclic directed graph.My question is will Floyyd Warshall give correct answer if I make the following initial condition in the adjacency matrix ?

1. Adj[i][j]=0 if i=j
2. Adj[i][j]=-1*INF if i!=j and there is no edge between node i and j
3. Adj[i][j]=w[i][j] otherwise, where w[i][j] is weight of edge between node i and j

The weights of edge can be positive and negative.

Answer 1

Yes, Floyd Warshall can give a correct answer for your problems, can be proved like using Floyd Warshall to find the shortest path between all pairs in graph. Or you can multiply each edges with (-1), and solve your problem like finding the shortest path between all pairs, then multiply your result with (-1).

But you can sort graph topologically, then use dynamic programming to calculating, which has complexity is max(|E|,|V|) instead of |V|^3 of FW.