Build Railway Sleeper Wall

minimum cost in a multistage graph.

A multistage graph G = {N, A} is a directed graph which can make a partition of the set of nodes or vertices N k (≥ 2) disjoint sets Ci, 1 ≤ i ≤ k, where the whole graph arc (n, m) is such that n belongs to m Ci Ci belongs to +1 for some i, 1 ≤ i ≤ k - 1. The cost of each arc (i, j) is provided by the function c. The sets C1 and Ck have a single node, calling the first source node (o) and the second destination node (d). If the number of sets k Ci is said to be a k-stage graph.
The problem is to find a minimum cost path to go from the source node or destination node d. For restrictions, minimum cost path will have exactly one node in each set Ci, Ci hence each define a stage graph. You can also say that each arc of the road joins with the next stage.
This issue has great practical significance since many of the problems of optimum allocation of resources can be formulated in terms of a multistage graph.
Consider how to apply dynamic programming to this situation:
It satisfies the principle of optimality as the minimum cost path must contain subpaths of the lowest cost; otherwise, these subpaths may be replaced with better ones, resulting in a total way of lower cost. In addition, the final solution will be a sequence of decisions, each decision depends on the outcome of others. In general, the i-th decision is to determine from a node or Ci, a bow or as having a source node and one or +1 from Ci +1 and the destination node, where 1 ≤ i ≤ k - 2. The minimum number of decisions for a k-stage graph is k - 2 and that every path has k - 1 arcs, and the latter is determined by the decision taken at the previous stage. Sea

CA (i, j) a minimum cost path COST E (i, j) from the source node to node j or Ci. Using a backward formulation we




Similarly, we can analyze the cost by making forward:
if CA (i, j) is a path of minimum cost COST (i, j ) from the node j of the set Ci to the destination node d, then:



In general, anyone may use either of the two formulations. Let's look at the algorithm that allows us to construct the minimum cost path back to a formulation. (We deleted the first index of the variable COST and we thought that it was important for the algorithm.)

multigraph algorithm (ENT A: arcs, k, n: integer; C: table [1 .. n, 1 .. n]; SAL P: table [1 .. k]) {
This algorithm builds on a graph of k stages with n vertices,
set of arcs A and C costs the least cost path P}






To study the complexity of this algorithm must take into account the complexity of the first loop will be O (max (n, a)) = O (n + a) where n is the number of vertices and the number of edges, and the second O (k) where k is always less than n. Therefore, overall complexity of the algorithm is O (n + a).