Multistage Graph Problem

This problem is solve by using dynamic programming method. Multistage Graph is a directed weighted graph. All vertices are divided into stages in such a way that vertex are connected to one edge to another edge.Note first stage and last stage are represented as a single vertex from source and sink of a graph.

Let we understand the working of multistage graph problem by the help of example.