Given A Graph G V E And E G E Let S T E V Suppose We Want To Check If There Exis

All the requirments are in the picture…………………………

3. Given a graph G = (V, E) and E’ g E. Let s,t E V. Suppose we want to check if there existsa path in G that starts at s and ends at t and contains at least one edge in E’. The followingalgorithm claims to returns true is such path exists and false otherwise. Note that this algorithm rehes on using BFS as a subroutine. BFS takes as input a graph(V, E) with starting and ending points 5, t and returns the shortest path from s to ii. (If you areinterested in exactly how BFS works, we will cover it briefly in the slides and it is in your bookon page 791. For this problem, we can just assume that it will correctly return the shortestpath.) procedure PathC’heck (V, E, E’, s, t) p = BFS(V, E,s,t)for each edge e in p:if e E E’ return true P‘F‘WNE‘ return false Is the algorithm above correct? Prove or give a counter-example.

Prof. Angela


Calculate Price

Price (USD)
Open chat