How to check u-v can be arbitrarily negative length using Floyd Warshall algorithm?

Правка en1, от nvson2201, 2021-01-23 20:46:53

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский nvson2201 2021-01-23 20:47:12 0 (published)
en1 Английский nvson2201 2021-01-23 20:46:53 730 Initial revision (saved to drafts)