All Shortest Paths using Floyd warshall's algorithm

Open Emmanuel-PLF opened this issue 7 years ago • 7 comments

Floyd's algorithm can be interesting when graph density is high (more edges than vertex).

Dec 30 '17 22:12 Emmanuel-PLF

how does this compares to this: https://github.com/backtracking/ocamlgraph/pull/63

Mar 12 '18 08:03 UnixJunkie

I might give a try at this implementation and report about it.

Mar 12 '18 08:03 UnixJunkie

Is there something needed so that this PR could be accepted?

Mar 13 '18 00:03 UnixJunkie

Is it normal to get NegativeCycle when my graph has only edges of length 1? adding 0 1 adding 0 5 adding 1 2 adding 2 3 adding 3 4 adding 4 5 Fatal error: exception Graph.Path.FloydWarshall(G)(W).NegativeCycle @Emmanuel-PLF

Mar 13 '18 03:03 UnixJunkie

My graph is undirected, has 6 nodes connected in a ring.

Mar 13 '18 03:03 UnixJunkie

Also, there is already the Johnson algorithm in ocamlgraph.

Mar 13 '18 06:03 UnixJunkie

@slindley

Mar 13 '18 06:03 UnixJunkie