3) Suppose you are given a digraph G = (V, E), edge weights wi, where i = 1, ...

Question

3) Suppose you are given a digraph G = (V, E), edge weights wi, where i = 1, ..., E and each edge weight is a positive integer number. Consider the following algorithm.

- Read the digraph G and the weights of the edges-
- Replace each edge of G, ei = uwi v, where i = 1, ..., E with a directed path with u at the beginning, v at the end and wi - 1 new nodes in between; i.e.,each edge uwi v in the original graph gets replaced by a directed path uv1…vwi -1v.
- Carry out BFS starting at a node s and keeping track of the number of edges used to reach each reachable node
- Output the distances -number of edges- used to reach each reachable vertex from s

i) Does this algorithm correctly finds the shortest paths from s to each reachable vertex?

ii) What is the asymptotic time complexity of this algorithm?

Explanation / Answer

i)no,it not finds the shortest paths from s to reachable vertex,because bfs is used for find out shortest path between unweighted graphs

ii)O((E + V) log V)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.