Bellman-ford course notes

[John Tan]

Hi:

On the notes "Graphs PART III" - Page 19 of the PDF file - the example
doesn't match the code example given (bellman_ford.c) I ran the program
and after the first iteration (i = 1) the value for D was: 0,6,4,2,7

But in the example (pdf notes), when i = 1, two nodes are still set to INF.

Which way is correct?

Also, regarding difference constraints, I copied down in class (as well as
another friend) the arrows pointing in the opposite direction compared to
the web notes? Is the web notes correct or do the arrows go the other way
for difference constraints? (Eg. Pg 12 on "Graphs PART IV" (PDF Version))

Thanks so much!

[Jim Clarke]

Post by John Tan
On the notes "Graphs PART III" - Page 19 of the PDF file - the example
doesn't match the code example given (bellman_ford.c) I ran the program
and after the first iteration (i = 1) the value for D was: 0,6,4,2,7
But in the example (pdf notes), when i = 1, two nodes are still set to INF.
Which way is correct?

Both -- but they're not consistent with each other. Iterative algorithms
often come in two flavours: update immediately and update when the whole
iteration is done. The code is "immediately" and the example is "when
the iteration is done".

Post by John Tan
Also, regarding difference constraints, I copied down in class (as well as
another friend) the arrows pointing in the opposite direction compared to
the web notes? Is the web notes correct or do the arrows go the other way
for difference constraints? (Eg. Pg 12 on "Graphs PART IV" (PDF Version))

The arrows should go from the node that has the -1 to the node with the
+1 in the constraint equation.
--
Jim Clarke -- Dept. of Computer Science, University of Toronto
http://www.cs.utoronto.ca/~clarke

[John Tan]

Thank you so much Prof. Clarke for answering so quickly - I really
appreicate it! Thanks!

Post by Jim Clarke

Post by John Tan
On the notes "Graphs PART III" - Page 19 of the PDF file - the example
doesn't match the code example given (bellman_ford.c) I ran the program
and after the first iteration (i = 1) the value for D was: 0,6,4,2,7
But in the example (pdf notes), when i = 1, two nodes are still set to INF.
Which way is correct?

Both -- but they're not consistent with each other. Iterative algorithms
often come in two flavours: update immediately and update when the whole
iteration is done. The code is "immediately" and the example is "when
the iteration is done".

Post by John Tan
Also, regarding difference constraints, I copied down in class (as well as
another friend) the arrows pointing in the opposite direction compared to
the web notes? Is the web notes correct or do the arrows go the other way
for difference constraints? (Eg. Pg 12 on "Graphs PART IV" (PDF Version))

The arrows should go from the node that has the -1 to the node with the
+1 in the constraint equation.
--
Jim Clarke -- Dept. of Computer Science, University of Toronto
http://www.cs.utoronto.ca/~clarke