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.

 1def 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
12def 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
29if __name__ == '__main__':
30    main()

Output:

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