Edit the RMarkdown source file for this assignment in RStudio. When you finish, Knit the file to HTML and upload the .html output to Canvas.

  1. Give an example of a graph with negative edges on which Dijkstra’s Algorithm never terminates. Explain why the algorithm fails to terminate.

  2. For the generic MetaSSSP algorithm, explain why, if pred(s) ever changes after InitSSSP, then the input graph contains a negative cycle through \(s\).

  3. In the generic MetaSSSP algorithm, the tense edges can be relaxed in any order you choose. Let \(P\) denote the current graph of predecessor edges \(\text{pred}(v)\rightarrow v\), and let \(X\) denote the set of all currently tense edges; both of these sets evolve as the algorithm executes.

    1. Prove that, if the input graph has no negative cycles, then \(P \cup X\) is always a dag.
    2. Prove that, if \(P \cup X\) is always a dag, then the input graph has no negative cycles.