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?
question from:
https://stackoverflow.com/questions/65862296/how-to-check-u-v-can-be-arbitrarily-negative-length-using-floyd-warshall-algorit 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…