10806 - Dijkstra, Dijkstra.

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

Moderator: Board moderators

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Wed Aug 23, 2006 10:21 pm

ayon wrote:can anyone verify whether my algorithm is correct? i am getting wa, i checked all inputs posted in this board.

- assign capacity 1 to each edges of the graph and simply run maxflow
- if maxflow < 2 then Back to jail
- remove edges where no flow occured(i.e where still have residual capacity)
- run dijkstra, get cost1
- remove dijkstra edges
- run dijkstra again, get cost2
- output cost1+cost2

please give me some counter-example if you find, or some more test cases, thanks
Your algo doesn't work for misof's test case posted above. If you remove the edges 1-3 and 2-6 in the third step, you will not find the optimal solution: 1-3-6 and 1-2-6.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Wed Aug 23, 2006 11:10 pm

misof's test case says
6
8
1 2 1
2 3 1
3 6 1
1 4 100
4 5 100
5 6 100
1 3 10
2 6 10

if we flow from 1 to 6, maxflow will be 3(i assigned capacity 1 to each edges), there is no way to remove 1-3 or 2-6 at step 3. at step 3 only edge 2-3 will be deleted as no flow occured in edge 2-3, and by running dijkstra twice 1-2-6 and 1-3-6 will be found.

anyway, i found my mistake, thanks for reply
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Neriman
New poster
Posts: 1
Joined: Sat Sep 16, 2006 12:48 pm

10806 WA

Post by Neriman » Sat Sep 16, 2006 1:03 pm

I keep getting WA for 10806 problem, and my output is correct for any possible input I could think of. Can anyone, PLEASE, help me with some tricky testcases?

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Fri Mar 02, 2007 5:04 pm

message to misof!!
actually you don't need to use bellman-ford algorithm
at first i got wa ( i used dijkstra then set used arcs as infinity and used dijkstra again) , then i read your advise and used dijkstra then set used arcs as infinity then negated arcs and finally used bellman-ford, i got AC
but..
for curiosity
i tried to use dijkstra instead of bellman-ford and got AC too, with almost 10-times shorter CPU time
i thought dijkstra doesn't work with negative values..
why then?
keep it real!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Mar 02, 2007 8:45 pm

message to misof!!
actually you don't need to use bellman-ford algorithm
Of course, as it's a min-cost max-flow problem. Some of the faster algorithms for it do use Dijkstra instead of Bellman-Ford with help of a clever transformation of the graph. Check nnahas' links.
i thought dijkstra doesn't work with negative values..
why then?
If you let Dijkstra's algorithm to visit the same vertex multiple times (it happens when there are negative weights), then it'll work correctly, as long as there are no negative cycles. But it would hurt its worst case runtime -- there are graphs on which it takes exponential time.
That's why people say that Dijkstra doesn't work with negative weights.

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Sat Mar 03, 2007 1:37 am

thx for your explanation
i'll find out more and compare the results, cause problem isn't so hard, so it could be the best way to study;)

regards
keep it real!

User avatar
N@$!M
New poster
Posts: 10
Joined: Wed Jan 10, 2007 7:26 pm

10806 Wrong Answer

Post by N@$!M » Mon Sep 17, 2007 11:53 am

I have used Dijkstra.
I have Read the Post of Misof in the board But didn't understand How to initialize the cost/weight-matrix .
I have Initialized The Weight-Matrix as follows:
For each edge (a,b) I have set W[a] = W[a] = dist :-?
Then I have (tried to) find the first shortest path using Dijkstra.
Then I have negated the weights of all the edges of this first path.
Then again I have (tried to) Find the next path using Dijkstra.

I got WA.
Help Me.

I Have Checked All the I/Os found on the BOARD.


Here Is My Code:

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#define INF 2147483640
#define num 120

long d[num],p[num] , q_count;

long w[num][num]  , cost;

long dequeue(long Q[])
{
	long item = Q[1] ,i;
	for(i=1;i<q_count;i++)
	{
		Q[i] = Q[i+1] ;	
	}		
	q_count--;
	return item ;
}

void enqueue(long Q[], long item)
{
	long i,j;
	for(i=1;i<=q_count;i++)
	{
		if(d[Q[i]] > d[item] )
		{
			for(j=q_count+1;j>i ;j--)
			{
				Q[j] = Q[j-1] ;	
			}			
			break;	
		}			
	}	
	Q[i] = item ;
	q_count++ ;
}

void Dijkstra(long s,long n)
{
	long i,j  ,Q[num] ,u;
	bool done[num] , inque[num];
	
	for(i=1;i<=n;i++)
	{
		d[i] = INF ;
		p[i] = -1;		
		inque[i] = false;
		done[i] = false;
	}
	
	d[s]  =  0;
	q_count = 0;
	enqueue(Q,s);
	inque[s] = true;
	while(q_count>0)
	{
		u = dequeue(Q);
		
		done[u] = true;
		for(i=1;i<=n;i++)
		{
			if(!done[i])
			{
				if(w[u][i] != INF)
				if( (d[u] + w[u][i]) < d[i])
				{
					d[i] = d[u] + w[u][i];
					p[i] = u;					
					if(!inque[i]){
						enqueue(Q,i);						
						inque[i] = true;
					}
				}					
			}				
		}	
	}	
}

void print_path(long i)
{	
	if(i != 1 )
	{
		if(p[i] == -1)
		{
			cost = INF;
			return;			
		}			
	}
	if(p[i] != -1)
	{
		cost += w[p[i]][i];
		w[p[i]][i] = INF ;
		w[i][p[i]] = 0-w[i][p[i]] ;
		print_path(p[i]);	
		//printf("%ld -- >",p[i]);		
	}	
}

int main(void)
{
	//freopen("10806.txt","r",stdin);
	long i,j,n,e,a,b,dist ,to;
	
	while(scanf("%ld",&n)==1)
	{
		if(n==0) break;
			
		scanf("%ld",&e);
		for(i=1;i<=n;i++)
		{
			for(j=i;j<=n;j++)	
			{
				w[i][j] = w[j][i] = INF;	
			}
		}			
		for(i=1;i<=e;i++)
		{
			scanf("%ld%ld%ld",&a,&b,&dist);
			w[a][b] = dist;	
			w[b][a] = dist;			
		}	
		
		Dijkstra(1,n);	
		
		cost = 0;
		print_path(n);		
		//printf("%ld\n Cost = %ld\n",n,cost);
		Dijkstra(1,n);
		print_path(n);
		
		if(cost < INF)
			printf("%ld\n",cost);
			//printf("%ld\n%ld\n",p[i],cost);			
		else 
			printf("Back to jail\n");
	}
}
"I AM NOT SURE WHETHER I SHOULD BE CONFUSED OR NOT..."
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet- 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.
Bangladesh.

e-Mail Address:
tariqmnasim@gmail.com

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Post by mmonish » Thu Oct 04, 2007 6:05 am

>> N@$!M

Are u sure that the dijkstra will work for finding the second shortest path?
Use Bellmanford algorithm to find the second shortest path bcoz edge weights r negetive.

Hope this helps.

asmaamagdi
New poster
Posts: 27
Joined: Tue Dec 20, 2005 9:14 am
Location: Egypt

Post by asmaamagdi » Wed Oct 24, 2007 6:58 pm

Hey guys.
I'm getting lots of WAs to this problem though I think my algo is right.

I first use dijkstra to find the first shortest path.
Then I mark each of its edges as invalid edges.
I use dijkstra again and use only valid edges this times.

This gave me WAs :(

The only bug I thought of was that I didn't mark the inverse edges as invalid edges. (if the first path contains edge 2 3, then I can't use 3 2 in the second path).
I modified my code to mark the inverse of the edges too but still WA :(

Please someone tells me if my idea is right or wrong.
and can someone please explain to me where the negative weighted edges are, or why you make any edge a negative weighted edge. How could this help ??!!

Thanx in advance :D
---
Asmaa Magdi

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Wed Oct 24, 2007 11:10 pm

Read carefully entire topic, there's a critical input above for your algo, which let you know why your idea is wrong..
keep it real!

Post Reply

Return to “Volume 108 (10800-10899)”