6 views

Skip to first unread message

Nov 7, 2012, 10:48:05 AM11/7/12

to cs561-f12

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu