All-Pairs Shortest Paths Problem is a problem of interest as it has many practical uses. One example is to make table of distance between all pairs of cities for a road atlas. Dynamic Programming is a powerful technique that can be used to solve this problem. It is because the problem has the overlapping sub-problems property and optimal sub-structure property, both are properties required so that the problem can be solved using Dynamic Programming technique. Overlapping Sub-problems is one thing that can make other technique such as Divide and Conquer to yield algorithm with exponential time complexity, because it always re-compute the same sub-problems. The power of Dynamic Programming is that it uses bottom up approach and memoization that ensure the same sub-problem is computed only once and the result is stored for later use. No need for a re-compute. This paper explains the application of Dynamic Programming in solving the All-Pairs Shortest Paths Problem.