Please give some test

Why BFS doesn't work ? Can you give some tests ?

6 9
5 6
3 4
2 4
1 5
3 6
1 2
1 6
4 5
3 3

i make a shortest path tree (i know i do it correctly) from the every vertex of the graph, but even that is giving me a WA on #17... can someone please give me a test case where that would fail?

@Todor
BFS won't work in a case like
6 6
1 2
2 5
1 3
3 5
3 6
3 4

if you make a BFS tree by searching the lower indexed vertices, starting from 1, then 5 would be committed under 2 where as it should be committed under 3,
even if you are constructing a tree from 3 in the above case i am sure a case can be formed that the above anomaly is exploited.

I have WA #17 too. But I don't understand why in your test BFS doesn't work?
6 6
1 2
2 5
1 3
3 5
3 6
3 4
My prog gives this answer:
1 2
1 3
3 4
3 5
3 6
It's correct, isn't it?

its correct.. yes..
i am saying that a BFS would construct the shortest paths for sure, but it would do so in a greedy format that will most probably give a graph with a sub-optimal diameter, so perhaps will a shortest path tree.. i even tried constructing the BFS with highest degree first but none of it seems to work..

any idea?

Look at the test, given by Victor (thanks him):
6 9
5 6
3 4
2 4
1 5
3 6
1 2
1 6
4 5

Answer will be
1 5
2 4
3 4
5 4
6 5
and maximum distance equal 3 (in edges), not 4!

How are you may start BFS programming
without mathematical characterization of
optimal solution. I found with difficulties
in internet that it is tree of shortest pathes
from absolute centre of graph.
Thus you need in two programs
1) Finding absolute centre(Hacimi)
2) Dejkstra for shortest paths.

P.S. Glad to confirm with help of 1569 My Hakimi algorithm realization.
But, of course, we don't need Hakimi algo to solve this problem. When edges have equal wheightes absolute centre
or in vertex or in middle of the edge.


Edited by author 02.06.2008 16:18

I have found algo here:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5609

Thanks Victor for his test, I've found a bug (as usual, I used some outer loop variable inside inner loop. ARGHHHHH!)

Edited by author 14.08.2008 14:01

Edited by author 14.08.2008 14:01

What is the complexity of Hakimi algo?

I repeat! You don't need Hakimi algo!
Apply your shortests path algo also to the middles of the edges as sink of searching.

My program gave the following output:

1 5
3 6
1 2
1 6
4 5

Is that correct?