True or False. Explain why

A longest simple path from s to t is defined to be a path from s tot 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 A longest simple path from s to t is defined to be a path from s tot 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