Question

ive an example of a simple, undirected graph that has a single source shortestpath tree which breadth-first search will not return for any ordering of its vertices.Your answer must

(a) Specify the graphG= (V, E)by specifying V and E.

(b) Specify the single source shortest path treeT= (V, ET) by specifying E T and also specifying the roots∈V.

(c) and include a clear explanation of why the breadth-first search algorithm we discussed in class will never produce T for any orderings of the vertices.

Answer 1

(a)An arbitrary vertex could lay closer to the ’center’ of the graph, hence the BFS depth will be underestimating the diameter. For example, in graph G = (V, E) = ({a, v, b}, {(a, v),(v, b)}), a BFS from v will have depth 1 but the graph has diameter 2

(b)

If the greatest number of edges on any shortest path from the source is m, then
the path-relaxation property tells us that after m iterations of BELLMANFORD, every vertex v has achieved its shortest-path weight in v.d. By the
upper-bound property, after m iterations, no d values will ever change. Therefore, no d values will change in the (m+ 1)st iteration. Because we do not know
m in advance, we cannot make the algorithm iterate exactly m times and then
terminate. But if we just make the algorithm stop when nothing changes any
more, it will stop after m + 1 iterations.
   BELLMAN−FORD−(M+1)(G, w, s )
   INITIALIZE−SINGLE−SOURCE(G, s )
   changes = TRUE

   while changes == TRUE
       changes = FALSE
       for each edge (u, v) ∈ G.E
           RELAX−M( u , v , w)
   RELAX−M( u , v ,w)
   if v.d > u.d+w(u,v)
v.d = u.d + w(u,v)
v.π = u
changes = TRUE
The test for a negative-weight cycle (based on there being a d value that
would change if another relaxation step was done) has been removed above,
because this version of the algorithm will never get out of the while loop unless
all d values stop changing

(c)

• Every time we want to find what are the edges adjacent to a given node ‘U’, we have to traverse the whole array AdjacencyMatrix[U], which is of length |V|.
• During BFS, you take a starting node S, which is at level 0. All the adjacent nodes are at level 1. Then, we mark all the adjacent nodes of all vertices at level 1, which don’t have a level, to level 2. So, every vertex will belong to one level only and when an element is in a level, we have to check once for its adjacent nodes which takes O(V) time. Since the level covers V elements over the course of BFS, the total time would beO(V * V) which is O(V²).
• In short, for the case of Adjacency Matrix, to tell which nodes are adjacent to a given vertex, we take O(V) time, irrespective of edges.
• Whereas, when Adjacency List is used, it is immediately available to us and it just takes time complexity proportional to adjacent nodes itself, which upon summation over all nodes V is E. So, BFS when using Adjacency List gives O(V + E).