Creating simple path edges not contained in BFS

First off...here's the problem...

Give an example of a directed graph G = (V, E), a source vertex s in V, and a set of tree edges F contained in E, such that for 开发者_运维知识库each vertex contained in V, the unique simple path in the graph (V, F) from s to v is a shortest path in G, yet the set of edges F cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.

Now...since this IS homework, I don't want a straight-out answer, but more of ideas for things to look at/try. But, here's what I've thought of so far...

I've basically figured that I can create a graph that has several shortest paths to a particular vertex. Of course, one of those paths would be found in the BFS. But, I can use one of the alternate routes to fit into F. However, the part that is throwing me off is the "no matter how the vertices are ordered"... I'm not sure how to include that in to my process. I've tried loops, various different directional flows, and nothing yet.

Any other ideas?

    3
 s ---- x
 |     /  
1|    / 1
 |   /
 |  /
 y

In case the above picture doesn't show

Assume

E = { ((s, x) : 3), ((s, y) : 1), ((y, x) : 1) }

where the two-tuples are ordered pairs with weights attached.

The edge set F = { (s, y), (y, x) } contains all the vertices of the graph. Further, the unique simple path it contains from s to x is the shortest path in the graph from s to x. However, F will never be found by a BFS.

Starting from s, x and y will be discovered and marked gray. Then, when y is explored, it will only find one other gray vertex, i.e. x, and not add it as a descendant in the resulting breadth-first tree.

I am not sure whether you are just to find a counter-example, or find an algorithm running on any given graph. Finding a counter-example is not very difficult, for example,

  0
 / \
1   2
|\ /|
| x |
|/ \|
3   4

The source is 0. The edge set F contains (0,1) (0,2), (1,3), (2,4). F cannot be produced by BFS.

I haven't found a general algorithm for any graph, but maybe the above sample can provide a clue.

The question is old, but I am posting another answer because it has been viewed many times. This is question 22-2.6 in Cormen/Leiserson/Rivest/Stein's Algorithms book and is likely to be encountered by others.

The responses above assume that the graph is weighted. BFS can produce the edge set in either response if the graph is taken as unweighted. The problem does not say that the graph is weighted, and in Cormen it is in a section about unweighted graphs.

Here is a solution in the unweighted case. The steps are:

1. Take a graph that goes out from the source s to 2 vertices x and y. s has out-degree 2. x and y each go out to a and b and nowhere else.
2. Your tree that is unreachable by BFS is from s to x, from x to a, then from s to y, and y to b.

It works because a and b have the same distance from x and y. If you enqueue x first, then your path via BFS will be from x to both a and b. If you enqueue y first, then your path via BFS will be from y to both a and b. In BFS you cannot mix and match the way the solution does.