longest path between two nodes for directed acyclic graph?

[Tyler Kahn]

I've seen it suggested that one could use the Bellman-Ford algorithm
with 'inverted weights'. I don't exactly know what this means or know
how to do this with networkx.

Can anyone help me out?


Thanks!!

[Ben Edwards]

So if you have a Graph G with nodes N and edged E and if each edge has
a weight w, you can instead set that weight to 1/w, and use the
Bellman Ford algorithm for shortest path, or one of the other
algorithms for shortest path in the networkx package. If it is a
directed-acyclic graph with no weights you should be able to use the
algorithm here:

http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_acyclic_graphs

with the weights set to 1.

Ben

[irinag]

but is there a bellman-ford implementation in networkx? I couldn't
find... thanks!

On Jul 21, 5:41 pm, Ben Edwards <bjedwa...@gmail.com> wrote:
> So if you have a Graph G with nodes N and edged E and if each edge has
> a weight w, you can instead set that weight to 1/w, and use the
> Bellman Ford algorithm for shortest path, or one of the other
> algorithms for shortest path in the networkx package. If it is a
> directed-acyclic graph with no weights you should be able to use the
> algorithm here:
>

> http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_a...

[Aric Hagberg]

On Thu, Jul 22, 2010 at 11:40 AM, irinag <irina.n...@gmail.com> wrote:
> but is there a bellman-ford implementation in networkx? I couldn't
> find... thanks!

There isn't. But if your weights are non-negative you can use
Dijkstra's algorithm: use shortest_path(G,source).

Aric

[Ben Edwards]

Bellman-ford is advantageous because it works on graphs with negative
weight edges, which now that I think about it might have been the
notion of inversion that was suggested to you at first, additive
inversion as opposed to mutliplicative inversion.

There is no Bellman-ford currently in networkx. Dijkstra's algorithm
works if your graph has no negative weights. The floyd-warshall
algorithm will work if you choose to give the graph edges negative
weights, but be warned it seems to give odd answers when a negative
cycle exists. Both Dijkstra's and the Floyd-Warshall algorithm are
implemented in networkx.

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Ben

[irinag]

Thank you very much for your replies! But do these methods work only
for DAG, not if you have cycles?

[Ben Edwards]

Correct. If you had a cycle in a graph, the longest path wouldn't be
well defined, because you could keep going round and round the cycle
making the path longer.

Ben

[Tyler Kahn]

Hmmm. I'm getting


TypeError: shortest_path() got an unexpected keyword argument
'weighted'

for

nx.shortest_path(G, source=b[0], target=b[-1], weighted=True)

On Jul 22, 1:58 pm, Aric Hagberg <ahagb...@gmail.com> wrote:

[Aric Hagberg]

On Fri, Jul 23, 2010 at 5:40 PM, Tyler Kahn <tka...@gmail.com> wrote:
> Hmmm. I'm getting
>
>
> TypeError: shortest_path() got an unexpected keyword argument
> 'weighted'

You probably have an older version of NetworkX.
You can find the version with
print networkx.__version__

Aric

[Loïc Séguin-Charbonneau]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I just added the Bellman-Ford algorithm to the development trunk of NetworkX. You can check it out right now or wait until NetworkX 1.3 is released.

For your specific problem, suppose you have a graph G with some arbitrary weights (positive or negative). Build another graph H as such

H = nx.Graph(G)
for u, v in H.edges():
H[u][v]['weight'] *= -1

Then run the Bellman-Ford algorithm on H. It will return a shortest path on H which corresponds to a longest simple path on G. This works for DiGraph as well.

If you graph G has a cycle with positive weight, i.e., if you sum the sum the weights of all the edges while going around the cycle and get a positive result, you'll have a negative weight cycle in H. Bellman-Ford will raise an exception indicating the presence of that negative weight cycle. This means that your graph G does not have a longest path, more precisely, you can find a path of length arbitrary long if you go around the cycle again and again.

Hope this helps,

Loïc

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (Darwin)

iEYEARECAAYFAkxXEVoACgkQLKWiTxa2C80T2wCgrgXr4nlKOIhPVPBeGcJvUqzx
wZ4AoLcF6l8SVvGwNXWSMPI41X6LiOj+
=PUYe
-----END PGP SIGNATURE-----