Give an example of a directed graph G (V, E), a source vertex s V, and a set of tree edges E E such that for each vertex v V, the unique path in the graph (V, E ) from s to v is a shortest path in G, yet the set of edges E cannot be produced by running BFS on G, no matter how the vertices are order...

The edges in E are shaded in the following graph To see that E c ...

Give an example of a directed graph G = (V, E), a source vertex s V,

Question:

Give an example of a directed graph G = (V, E), a source vertex s ¬ V, and a set of tree edges E π ¬ E such that for each vertex v ¬ V, the unique path in the graph (V, E π) from s to v is a shortest path in G, yet the set of edges E π cannot be produced by running BFS on G, no matter how the vertices are ordered in each adjacency list.