Dynamic Programming comes to the rescue. We need to restructure the algorithm so that a table of values is computed only once and then saved to be used to compute the larger values. Floyd's Algorithm Another popular graph optimization problem is All-Pairs Shortest Path. In this problem, you are to compute the minimal path from every node to every other node in a directed weighted graph. A directed graph uses arcs rather than edges to connect the nodes.
Arc are edges with a direction.
In the example below there is an arc from V2 to V3 but not from V3 to V2. The array shown below is a representation of the directed weighted graph. Each row and column represents a particular node in the graph, while each entry in the body of the array is the weight of an arc connected the corresponding nodes. Floyd's algorithm uses the Dynamic Programming Method to compute the shortest paths between every pair of nodes. This operation is repeated for each node Vi ,Vj and for each intermediate node Vk.