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