CODEWITHSUNDEEP
shortest-pathdirected-acyclic-graphsfloyd-warshall
remo
remo

Reputation: 898

All shortest paths in a DAG (directed acyclic graph)

I have a weighted DAG, with some negative edge weights, and want to find all shortest paths in it. Is there any algorithm with complexity better than O(n^2). (My graph is complete i.e. there is an edge (i,j), for any i,j in {1..n} and i < j ).

Thanks

Upvotes: 1

Views: 3815

Answers (2)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86146

The algorithm you're looking for is Floyd-Warshall, which runs in O(n3).

Sometimes you can do better than this by running Djikstra's on every node. Using a fibbonacci heap, you can get O(n2 log n + ne), where e = number of edges. It's even possible to get this to work with negative edge-weights!

However, fibbonacci heaps have large constants, so in practice, this approach will only be faster for very sparse graphs. Since you said your graph is complete, Floyd-Warshall is your best bet.

Upvotes: 1

Daniel Rivas
Daniel Rivas

Reputation: 256

Well, a popular algorithm for Path finding is A*. But you can check this article for more information:

Go to Article

Cheers

Upvotes: 1

Related Questions