Dynamic Programming Exercises

Bellman-Ford

  1. For each graph, for each iteration of the Bellman-Ford algorithm, for each vertex, display the distances to the bottom vertex (starting with the top vertex):
    Digraph 1:
    digraph: A 2-> B, A 4-> C, C -3-> B
    Digraph 2:
    digraph: A -4-> B, B 01-> D, B -2-> E, C 8-> B, D 6-> A, E -3-> C, A -3-> T, C 3-> T, D 4-> T, E 2-> T
    Digraph 3 (simple model of taking a job directly after high school or going to college first, so maximizing cost instead of minimizing it):
    digraph: Many vertices, each with a label indicating the total amount earned for 1) taking a $40000/year job at age 19 (with raises based on the percentage earned) and 2) going to college then making $65000/year (with raises based on the percentage earned)
    Digraph 4:
    digraph: A 5-> B, B 1-> C, B 2-> D, C 1-> E, D 2-> F, E -1-> D, F -3-> E

Last Modified: