SSSP Fact 3 proof

[Jared Saia]

Good morning!  It's a good day for science, math and education!

In lecture yesterday, I claimed that each time an edge was relaxed, the dist value of some vertex decreases at least by the minimum edge weight.

Someone in class (Stephen I think) gave a counterexample showing this is wrong. 

Instead what we can say is that every time an edge is relaxed, the dist value of a vertex must decrease by at least the value Delta defined below:

Delta is the smallest value > 0 such with the property that Delta = (sum of weights of edges in S1) - (sum of weights of edges in S2) for any two sets of edges S1 and S2

Note that Delta is at least 1 if all the edge weights are integers.  Moreover, Delta is a fixed constant even in the case where the edge weights are arbitrary real numbers.

Jared