If i have q query [start, end] in the graph. How to check whether:
the length of start to end can be arbitrarily negative length?
0 floydWarshall(matrix, n) // RUN THE FLOYD WARSHALL ALGORITHM 1 FOR (start, end) in q: 2 check = false 2 while(start != end) 3 start = Next(start) 4 if (dist[start][start] < 0) 5 check = true, break 6 if check == true 7 return "Negative Loop here"
I try the code like above and get Time limit because I have a while loop inside which is to find negative loop in the path from start to end.
Can you help me find another method?
not sure if I understand the problem because it seems kind of silly but all shortest-paths will be "arbitrarily negative" iff the graph contains any negative cycles at all
edit: actually, more information is necessary, I assumed that the graph was undirected and connected