Question:

Given a weighted, directed graph with n nodes and m edges, where each edge has an associated weight $($both positive and negative$),$ design an algorithm to determine if there is a negative weight cycle reachable from a specified starting node s$.$

A negative weight cycle is a cycle in the graph where the sum of the edge weights is negative. The algorithm should return True if such a cycle exists and False otherwise.

Provide a Python implementation and explain the approach in detail, including time complexity.

Constraints:

The graph has $1n5000$ nodes and $0m{10}^{{?}^{{?}^{?}}5}$ edges.

Edge weights range from $-{10}^3$ to ${10}^3.$

Function Signature:

Python

Copy codeExample:

Input:

Copy codeOutput: True $($There is a negative cycle: $1->2->3->1)$