Our instructions for this problem are as follows: By using the Bellman-Ford leas

Question

Our instructions for this problem are as follows:

By using the Bellman-Ford least-cost/shortened-path algorithm, complete the table by filling the Lh(n) and Path on each row to show the result of each iteration. Result of the last iteration with h = 4 is already provided in red as a way to help you to verify if your iterations are performed correctly.

----------

This is all of the information we are provided to answer the question. The reference to "Problem 2" is the only shared attribute, the network diagram, which is shown above the table.  

Problem 3. Repeat Problem 2 using the Bellman-Ford least-cost or shorted-path algorithm to the same network (shown again on the right for your convenience) Complete the table by filling the Lh(n) and Path on each row to show the result of each iteration. Result of the last iteration with h = 4 is already provided in red as a way to help you to verify if your iterations are performed correctly. 1 point each box, 20 points in total) 2 1 1 4 4 N5 hL2) Path Lh(3) Path Lh4 Path L5) Path Lh6 Path 3 1-2-5-33 1-2 1-2-5-4 2 1-2-5 5 1-2-5-3-6

Explanation / Answer

In Bellman-Ford algorithm,we first assign 0 weight to source vertex and infinity to all remaining vertices.

Then We check in every iteration to the adjacenr vertex if Do following for each edge n[i]-n[j]
………………If dist[n[j]] > dist[[n[i]] + weight of edge n[i]n[j], then update dist[n[j]]
………………….dist[n[j]] = dist[n[i]] + weight of edge n[i]n[j]

It continues for n-1 iterations where n is number of vertices.

In evry iteration we checked minimum of current value of L(h) and adjacent vertices nad length of new path, if length of new path is minimum then update the value of cell

h L(h2) PATH L(H3) PATH L(h4) PATH L(h5) PATH L(H6) PATH 0 1 1-2 INFINITY - INFINITY - INFINITY - INFINITY - 1 1 1-2 4 1-2-3 4 1-4 2 1-2-5 INFINITY - 2 1 1-2 3 1-2-5-3 3 1-2-5-4 2 1-2-5 6 1-2-5-6 3 1 1-2 3 1-2-5-3 3 1-2-5-4 2 1-2-5 5 1-2-5-3-6 4 1 1-2 3 1-2-5-3 3 1-2-5-4 2 1-2-5 5 1-2-5-3-6

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.