Let $D^{(k)}_{ij}$ restrict intermediate vertices to the first k. Its recurrence is $D^{(k)}_{ij}=\min(D^{(k-1)}_{ij},D^{(k-1)}_{ik}+D^{(k-1)}_{kj})$. Combining stored smaller subproblems is dynamic programming, C.
More Dynamic Programming questions
GATE 2016 CS (CS2) Q48– Matrices A₁,A₂,A₃,A₄ have dimensions 10×5, 5×20, 20×10 and 10×5. Find the minimum…
GATE 2011 CS (CS1) Q35– For A[0…n−1], define Lᵢ as the longest monotonically increasing run beginning at i. Set…
GATE 2011 CS (CS1) Q48– Matrices M₁,M₂,M₃,M₄ have dimensions p×q,q×r,r×s,s×t. With p=10,q=100,r=20,s=5,t=80, find…
GATE 2010 CS (CS1) Q44– The weight of a sequence a 0,,a n-1 is a 0+a 1/2++a n-1/2n-1. Subsequences preserve order…
GATE 2026 CS (CS2) Q39– Consider a table T where the entries T[i][j], 0 i,j n, represent costs of subproblems in a…
GATE 2024 CS (CS2) Q35– Let A be an array containing integer values. The distance of A is defined as the minimum…