Perform 2 iterations (ONLY!) using the Bellman-Ford Algorithm and comment on whe
ID: 3647860 • Letter: P
Question
Perform 2 iterations (ONLY!) using the Bellman-Ford Algorithm and comment on whether the solution has converged to the results obtained using the Dijkstra method.
Is your result dependent upon the selection of links made for processing with the Bellman-Ford method? Explain your answer using a different order of selection.
Explanation / Answer
Consider computations for one destination d Initialization Each node table has 1 row for destination d Distance of node d to itself is zero: Dd=0 Distance of other node j to d is infinite: Dj=?, for j? d Next hop node nj = -1 to indicate not yet defined for j ? d Send Step Send new distance vector to immediate neighbors across local link Receive Step At node j, find the next hop that gives the minimum distance to d, Minj { Cij + Dj } Replace old (nj, Dj(d)) by new (nj*, Dj*(d)) if new next node or distance Go to send step Now consider parallel computations for all destinations d Initialization Each node has 1 row for each destination d Distance of node d to itself is zero: Dd(d)=0 Distance of other node j to d is infinite: Dj(d)= ? , for j ? d Next node nj = -1 since not yet defined Send Step Send new distance vector to immediate neighbors across local link Receive Step For each destination d, find the next hop that gives the minimum distance to d, Minj { Cij+ Dj(d) } Replace old (nj, Di(d)) by new (nj*, Dj*(d)) if new next node or distance found. http://i50.tinypic.com/jpdhr7.png (picture)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.