nvson2201's blog

By nvson2201, history, 4 months ago, In English

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?

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nvson2201 (previous revision, new revision, compare).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If online gets TLE, try offline

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but the queries is online and i don't know whether have negative loops between them

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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