it has been said today that after the k iterration of BellmanFord we found all light weight paths from s to every vertix in the graph of at most k edges. is that right? if so, why?
Date: 30 Jun 2014 16:32
Number of posts: 6
RSS: New posts
What we proved in class as introduction (and proof) to BF is that if we use the "relax" method
on each edge of a shortest path by the order of them (starting with the closest to s,
we may "relax" other paths before, after, or between those as long as we "relax" those edges
in that order) then this shortest path (or another one with the same weight) will be in the
shortest paths graph returned by the algorithm.
(Another use of this very important theorem besides the proof of BF is the proof of the linear time
SSSP in DAGs that relaxes the edges by the topological order.)
Neither. (Or a "technically yes")
Running k iterations of BF will give us shortest paths that are at least better (or equal) to
any shortest path with no more than k edges, but may return us shortest paths with more edges.
If you want exactly to get the shortest paths with at most k edges, use a k-layered a-cyclic graph. (takes O(k*|E|+|V|))
אני חושב שלבנות גרף שכבות יתן לך בשכבה הקיי את המסלולים הקלים ביותר שאורכם בדיוק קיי,
בעוד שבגרף כללי האיטרציה הקיי תיתן לך באמת את המסלול הקל ביותר שאורכו לכל היותר קיי (אם המסלול הקל ביותר הכללי אורכו פחות מקיי אז אחרי עוד רלקסציות אנחנו לא נשפר אותו ולכן הוא יישמר)
This is correct - a good example is what we did at the start of tirgul 5… notice that if you relax the edges in the "correct" order, you have all the shortest paths of all lengths in one iteration of BF! BF guarantees that after iteration x, you will have found all shortest paths of length at most x, it is possible you found more.