CODEWITHSUNDEEP
algorithmshortest-pathdirected-acyclic-graphsfloyd-warshall
advocateofnone
advocateofnone

Reputation: 2541

Longest path between all pairs in a DAG

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.

Upvotes: 0

Views: 3765

Answers (1)

Anh Huynh
Anh Huynh

Reputation: 106

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.

Upvotes: 3

Related Questions