10449 - Traffic

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Feb 13, 2003 11:06 am

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 ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Feb 13, 2003 11:14 am

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..

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Feb 13, 2003 11:25 am

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,

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Feb 13, 2003 11:27 am

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.

Thanks,

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Feb 13, 2003 12:29 pm

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.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Fri Feb 14, 2003 12:48 am

turuthok - perhaps you have an error similar to the one i had. i used code like:

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

then
improve all paths

then.....
if(path<infinity)....

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'......

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Fri Feb 14, 2003 4:19 am

Caesum, ... that was it!! It was precisely what you mentioned in your comment.

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

Best regards,

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Fri Feb 14, 2003 5:57 am

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 :)

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

modified Bellman-Ford

Post by ChristopherH » Tue Apr 01, 2003 1:07 am

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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Apr 01, 2003 8:32 am

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?

Regards
Dominik
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

10449

Post by WanBa » Tue Jun 17, 2003 2:40 pm

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:
Last edited by WanBa on Thu Jun 19, 2003 5:25 pm, edited 1 time in total.
destiny conditioned by past

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » Tue Jun 17, 2003 4:27 pm

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
Last edited by Chow Wai Chung on Thu Jun 19, 2003 4:32 am, edited 3 times in total.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Jun 18, 2003 7:32 am

to both of us:
search board FIRST, and after that post our threads... answer for our questions are included in other threads

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » Wed Jun 18, 2003 9:56 am

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

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

Post by Chow Wai Chung » Thu Jun 19, 2003 3:22 am

I had solved this problem, my program have some problem on disconnect city before. :oops:

Post Reply

Return to “Volume 104 (10400-10499)”