Page 2 of 4

Posted: Thu Feb 13, 2003 11:06 am
by turuthok
Dominik, I think we share the same confusion here ...

I also added the check to return '?' if the junction number is out of range. Still doesn't help ... any other ideas ???

I also use Bellman-Ford algorithm for this. Unreachable junction will return '?'.

Thanks for any comment ...


Posted: Thu Feb 13, 2003 11:14 am
by Larry
You need to check for negative cycles as well. If there's a negative cycle, and you can get to it on the way to the destination, then you will definitely go under 3$, thus making it a "?". I missed this for awhile..

Posted: Thu Feb 13, 2003 11:25 am
by turuthok
Larry, I'm pretty sure I checked negative cycles as well. Correct me if I'm wrong but after I ran Bellman-Ford for n-cycles ... I would have a list of distances from junction 1 ... Whenever I see an element with < 3 ... I'll print '?'. Same output for unreachable junctions ...

Thanks for your comment,


Posted: Thu Feb 13, 2003 11:27 am
by turuthok
Is there a possibility that when there's a negative cycle to junction X ... the value of dist[X] after n-cycle is still positive ???

If it is then that must be the problem ... please comment.



Posted: Thu Feb 13, 2003 12:29 pm
by Adrian Kuegel
Yes, there is this possibility. I solved it by following the path from destination to source. For each node on the path I checked if I can reach with some edge from this node another node better. If yes, there must be a negative cycle.

Posted: Fri Feb 14, 2003 12:48 am
by Caesum
turuthok - perhaps you have an error similar to the one i had. i used code like:

path=infinity....... or (1<<30)

improve all paths


however this didnt work because i had been improving paths, and adding negatives to the infinity value i used, in the end i sorted it with

if(path<lower_inf)..... or (1<<29)....

(it only got added to the 'inf' value because there was a path from i to j which was negative weight and so this was an 'improvement'......

Posted: Fri Feb 14, 2003 4:19 am
by turuthok
Caesum, ... that was it!! It was precisely what you mentioned in your comment.

Guys, thanks for all the mind-opening comments ...

Best regards,


Posted: Fri Feb 14, 2003 5:57 am
by Whinii F.
I think that d can still be positive after the n-cycle Bellmann-Ford.
So I found all vertices which were in the condition

for all edges (u, v)
d[v] > d+w(u, v)

and marked all vertices which were reachable from v, with -INFINITE.

And Caesum's comments were essential. Thank you, Caesum! =)
(Actually wrote this reply to thank him :)

modified Bellman-Ford

Posted: Tue Apr 01, 2003 1:07 am
by ChristopherH
There's a nice simple modification to Bellman-Ford which will give perfect results in the presence of negative cycles without needing any postprocessing.

Simply run Bellman-Ford for 2n cycles (instead of n), but after the first n iterations start relaxing everything to -infinity (since anything which hasn't stabilized must be on a negative cycle). Within 2n cycles everything will have converged.

As usual, you can shortcut the process as soon as everything has stabilized.

Posted: Tue Apr 01, 2003 8:32 am
by Dominik Michniewski
Thanks for nice hint :)
BTW. It's neccessary to run to 2*N Bellman-Ford algorithm ? Maybe is enough to run this algorithm only N+1 times, and in N+1 run change states of every lengths, which vary to -infinity ?

Could anyone tell me: I'm right or I'm wrong?



Posted: Tue Jun 17, 2003 2:40 pm
by WanBa
thanx to both DM and Chung, I have found the bug in my pro , making sure the value of Len must not transcend the Limit.
But I wonder whether there are some improvement to accelerate
the running speed? :roll:

Posted: Tue Jun 17, 2003 4:27 pm
by Chow Wai Chung
I also use bellman-ford to do this problem, but i got many WAs.....

I had try many test cases, such as negative cycle, disconnect path.... But i still don't know what is my mistake, can anyone post some test data here??( which may helpful for me to find my mistake and got AC!!) :lol:

thank you very much

Posted: Wed Jun 18, 2003 7:32 am
by Dominik Michniewski
to both of us:
search board FIRST, and after that post our threads... answer for our questions are included in other threads

Best regards

Posted: Wed Jun 18, 2003 9:56 am
by Chow Wai Chung
Dominik, thank you for your remind.
But i had search for this problem on this board and consider those mistake may exist on my program before, but i still don't know where is my mistakes, and i found someone ask a new question on this problem, so i add my problem to this thread.

If anyone don't mind, please send me your test data. :D

Thank you

Posted: Thu Jun 19, 2003 3:22 am
by Chow Wai Chung
I had solved this problem, my program have some problem on disconnect city before. :oops: