Knapsack problem & all-pairs shortest path with matrix help NO CODING. ONLY WRIT

Question

Knapsack problem & all-pairs shortest path with matrix help

NO CODING. ONLY WRITE PSUEDO CODE PLEASE

Apply the bottom-up dynamic programming algorithm to the following instance of the knapsack problem for a knapsack of capacity W = 6: Solve the all-pairs shortest path problem for the digraph with the following weight matrix: [0 5 infinity infinity 3 2 0 infinity infinity infinity infinity 3 0 2 infinity 1 2 1 0 infinity 7 infinity infinity 3 0] Also draw the digraph whose weight matrix is given above.

Explanation / Answer

6. The pseudocode for solving the Knapsack problem is as follows using the dynamic programming approach.Here goes the approach:

Pseudocode:

Hence, this is the pseudocode for solving the knapsack problem using the dynamic approach.

7.The pseudocode for the All pairs shortest path problem is as follows:

Pseudocode:

for uu = 1 to NOB
for qq = 1 to NOB
if there is an edge from uu to qq
distance[0][uu][qq] = the length of the edge from uu to qq
else
distance[0][uu][qq] = INFINITY
  
for io = 1 to NOB
for uu = 1 to NOB
for qq = 1 to NOB
distance[io][uu][qq] = minimum(distance[io-1][uu][qq], distance[io-1][uu][io] + distance[io-1][io][qq])

Hence, this is the pseudocode for finding the shortest path problem also known by the name Floyd-Warshall's Algorithm.

Please rate the answer if it helped....Thankyou

Hope it helps....

Related Questions

Navigate

• Browse (All)
• Browse K
• Subjects

---

---

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