Briefly describe about multistage graph.
Subject Algorithm Design
NU Year Set: 2.(b) Marks: 5 Year: 2009

Multistage graph is a directed graph in which the nodes can be divided into a set of stages such that all edges are from a stage to next stage only (In other words there is no edge between vertices of same stage and from a vertex of current stage to previous stage).

We are given a multistage graph, a source and a destination, we need to find shortest path from source to destination. By convention, we consider source at stage 1 and destination as last stage.

 

Login to post your comment.