Single-Source Shortest Paths Exercises

   < Previous  Next >
  1. Choose a random group assignment:
    • Bellman-Ford (Section 22.1)
    • Single-source shortest paths in DAGs (directed acyclic graphs) (Section 22.2)
    • Dijkstra's (Section 22.3)
  2. In your group, do the following to explain your assigned algorithm:
    1. Give a description of your algorithm (in English). Include any constraints that the algorithm has.
    2. Provide pseudocode for your algorithm
    3. Detail the execution of your algorithm for each of the following graphs (with A as the source):
      G1
      digraph g{ A -> C [ label='9' ]; A -> D [ label='5' ]; A -> E [ label='8' ]; B -> A [ label='2' ]; B -> C [ label='1' ]; B -> E [ label='3' ]; C -> B [ label='7' ]; D -> A [ label='6' ]; D -> C [ label='3' ]; D -> E [ label='2' ]; E -> C [ label='6' ]; F -> C [ label='4' ]; }      		 G2
      digraph g{ A -> C [ label='9' ]; A -> D [ label='5' ]; A -> E [ label='8' ]; B -> A [ label='2' ]; B -> C [ label='1' ]; B -> E [ label='3' ]; C -> B [ label='-7' ]; D -> A [ label='6' ]; D -> C [ label='3' ]; D -> E [ label='2' ]; E -> C [ label='6' ]; F -> C [ label='4' ]; }      		 G3
      digraph g{ A -> C [ label='9' ]; A -> D [ label='5' ]; A -> E [ label='8' ]; B -> E [ label='3' ]; C -> B [ label='7' ]; D -> C [ label='3' ]; D -> E [ label='2' ]; F -> C [ label='4' ]; }
    4. Explain what the run-time of your algorithm is and why.

Last Modified: