1. (15 points) True or False. Decide whether these statements are True or False. You must briefly justify all your answers to receive full credit.

(a) (5 points) If some edge weights are negative, the shortest paths from s can be obtained by adding a constant C to every edge weight, large enough to make all edge weights nonnegative, and running Dijkstras algorithm.

(b) (5 points) Let P be a shortest path from some vertex s to some other vertex t. If the weight of each edge in the graph is squared, P remains a shortest path from s to t.

(c) (5 points) A longest simple path from s to t is defined to be a path from s to t that does not contain cycles, and has the largest possible weight. Given a directed graph G with nonnegative edge weights and two nodes s and t, the following algorithm can be used to either find a longest simple path from s to t, or determine that a cycle is reachable from s:

Negate all the edge weights.

Run Bellman-Ford on the new graph.

If Bellman-Ford finds a shortest path from s to t, return that as the longest simple path.

Otherwise, declare that a cycle is reachable from s. Assume t is reachable from s