When Dijkstra's algorithm is run on a graph with negative weights, it might not produce the correct answers, but it will still produce something. What values of D[v] and P[v] are produced when we run Dijkstra's algorithm (with the pseudocode as given in the lecture notes) to the graph on the lecture slide labeled "Bellman–Ford example", from starting vertex s? Are they correct?
Apply the reweighting step of Johnson's algorithm to the same graph. (You will have to name the added vertex something different than s, because the graph already has a vertex named s. You do not have to use Bellman–Ford to find the distances used in this reweighting step, as long as you use the correct shortest-path distances.)
If T is an undirected tree, with edge weights, then every pair of vertices can be connected by a unique path in the tree. Suppose you want to compute the distance of each vertex from some starting vertex s. Explain how to transform T into a directed acyclic graph with the same distances from s, so that the linear time DAG shortest path algorithm can be used for this problem. (It is also easy to solve the problem more directly but that is not the intended solution to this problem.)
If T is an undirected tree, with edge weights, and some of those weights are negative, then because T has no cycles it has no negative cycles. But the Bellman–Ford algorithm (in the form described in the lecture) will not work correctly for these graphs. Explain what goes wrong.