The Enterprise is in orbit around Starbase 325. An urgent medical situation requires that it travel as quickly as possib

[answerhappygod]

The Enterprise Is In Orbit Around Starbase 325 An Urgent Medical Situation Requires That It Travel As Quickly As Possib 1 (79.05 KiB) Viewed 53 times

The Enterprise is in orbit around Starbase 325. An urgent medical situation requires that it travel as quickly as possible to the distant planet Vertex T. In fact, the situation is so urgent that the Federation requests that the Enterprise arrive yesterday. Your goal is to determine if it is possible to get the Enterprise from s to t in negative total time, so that it arrives before it leaves. You have a directed graph G representing the Universe. Each known location in Federation space is a vertex in the graph. There are a number of hyperspace bypasses between these points. A hyperspace bypass from point u to point v is represented by the edge (u, v). The weight of the edge w(u, v) is equal to the amount of time that passes while traversing it. Notice that some bypasses run through some sort of crazy time-warp thing, causing the ship to travel back in time. (a) Explain why Dijkstra's algorithm cannot be used to solve this problem. (b) Suppose that G contains no negative weight cycles, describe an algorithm that returns TRUE if there exists a path from s to t with negative total weight and FALSE otherwise. Analyze the running time of your algorithm. (c) Lieutenant Data tells you that there is exactly one negative weight cycle present in G and provides you with the vertices that are in the cycle. Describe an algorithm that returns TRUE if there exists a path from s to t with negative total weight and FALSE otherwise. Analyze the running time of your algorithm.