Tweeted twitter.com/#!/StackCompSci/status/283435595538259969
2 fixing formatting, use latex, and provide simple reference.
source | link

bellman ford Bellman-Ford algorthm and negative cycle proof

I found the algorithm for finding the negative cycle in a graph after running Bellman-FordBellman-Ford algorithm. 

The algorithm is to perform another relax iteration over all the edges. Than if we find an edge to relax we stop and start to follow it parent vertex starting from V$V$ that u$u$ is its parent until we close a cycle.

ImI'm having little problem proving this... I want to prove now that no matter when I stop the algorithm - if p[v]=u$p[v] = u$ always d[v]<=d[u]+w(u,v)$d[v]\le d[u]+w(u,v)$ and to prove that a cycle in parent pointer is necessarily a negative cycle.

bellman ford algorthm and negative cycle proof

I found the algorithm for finding the negative cycle in a graph after running Bellman-Ford. The algorithm is to perform another relax iteration over all the edges. Than if we find an edge to relax we stop and start to follow it parent vertex starting from V that u is its parent until we close a cycle.

Im having little problem proving this... I want to prove now that no matter when I stop the algorithm - if p[v]=u always d[v]<=d[u]+w(u,v) and to prove that a cycle in parent pointer is necessarily a negative cycle.

Bellman-Ford algorthm and negative cycle proof

I found the algorithm for finding the negative cycle in a graph after running Bellman-Ford algorithm. 

The algorithm is to perform another relax iteration over all the edges. Than if we find an edge to relax we stop and start to follow it parent vertex starting from $V$ that $u$ is its parent until we close a cycle.

I'm having little problem proving this. I want to prove now that no matter when I stop the algorithm - if $p[v] = u$ always $d[v]\le d[u]+w(u,v)$ and to prove that a cycle in parent pointer is necessarily a negative cycle.

1
source | link

bellman ford algorthm and negative cycle proof

I found the algorithm for finding the negative cycle in a graph after running Bellman-Ford. The algorithm is to perform another relax iteration over all the edges. Than if we find an edge to relax we stop and start to follow it parent vertex starting from V that u is its parent until we close a cycle.

Im having little problem proving this... I want to prove now that no matter when I stop the algorithm - if p[v]=u always d[v]<=d[u]+w(u,v) and to prove that a cycle in parent pointer is necessarily a negative cycle.