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.