# multistage graph

🏠

Implementation of the dynamic programming calculation from the Multistage Graph lecture by Abdul Bari.

I never actually needed to build a multistage graph; instead this is really just a graph, for which nodes have no awareness of their stage.

Not extremely useful, but a good way to dip your toes into dynamic programming.

 1 def multistage_graph_minimum_cost(g):
2     def cost(i):
3         if i in memo:
4             return memo[i]
5         memo[i] = min(g[i][ind][1] + cost(n) for ind, (n, w) in enumerate(g[i])) if g[i] else 0
6         print(f"cost at {i} is {memo[i]}")
7         return memo[i]
8
9     memo = {}
10     return cost(1)
11
12 def main() :
13     g = {}
14     g[1] = [(2,9),(3,7),(4,3),(5,2),]
15     g[2] = [(6,4),(7,2),(8,1),]
16     g[3] = [(6,2),(7,7),]
17     g[4] = [(8,11),]
18     g[5] = [(7,11),(8,8),]
19     g[6] = [(9,6),(10,5),]
20     g[7] = [(9,4),(10,3),]
21     g[8] = [(11,8),(10,5),]
22     g[9] = [(12,4),]
23     g[10] = [(12,2),]
24     g[11] = [(12,5),]
25     g[12] = []
26
27     print(multistage_graph_minimum_cost(g))
28
29 if __name__ == '__main__':
30     main()


Output:

 1 cost at 12 is 0
2 cost at 9 is 4
3 cost at 10 is 2
4 cost at 6 is 7
5 cost at 7 is 5
6 cost at 11 is 5
7 cost at 8 is 7
8 cost at 2 is 7
9 cost at 3 is 9
10 cost at 4 is 18
11 cost at 5 is 15
12 cost at 1 is 16
13 16