For any vertex z not equal to x, you know the value of M[z, i-1], the length of

Question

For any vertex z not equal to x, you know the value of M[z, i-1], the length of the shortest path from x to z using i-1 or fewer arcs. Add to that A[z, v] and you have a path with one more arc from x to v. Find the shortest such path by trying all possible z's. Compare this with the shortest path of length i-1 from x to v, represented by M[v, i-1], and take the smaller value. Bellman-Ford Algorithm (n x n matrix A; source node x) Local variables: 2-D array n x n-1 array M //here entry M[v,i] represents the //shortest path from x to v //that uses no more than i arcs indices i, j vertices v, z //initialize M array for i = 0 to n - 1, set M[x,j] = 0 //shortest path from x to x of any //number of arcs is //always length 0 for v = any vertex not equal to x set M[v,1] = A[x,v] //shortest path of length l from x to y //is an arc from x to v for i from 2 to n-1 //successively more arcs in paths for v = any vertex not equal to x M[v,i] = min(M[v,i-1], min all z not equal to x (M(z,i-1] + A[z,v])) (a) Is this a greedy algorithm or a dynamic programming algorithm? If the former, where in the algorithm are you being greedy? If the latter, what are the optimal subproblems?

Explanation / Answer

Dijksra

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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