CODEWITHSUNDEEP
algorithmgraphbreadth-first-search
user3055419
user3055419

Reputation: 11

Modified breadth-first search on a graph with edge weights of 2, 3 or 5

Suppose that we are given a directed graph H = (V, E). For each edge e, the weight of the edge, w(e) is either 2, 3 or 5. Modify the BFS so that it will compute the length of the shortest path from a single source vertex s. Explain why your algorithm is correct and determine its worst-case running time (You may assume that H is represented via an adjacency list).

How would you go about this? What makes the specific weight edges different from just any?

Upvotes: 1

Views: 939

Answers (1)

Dragos Florian Ristache
Dragos Florian Ristache

Reputation: 115

You can consider imaginary nodes between the edges. So if between 2 nodes there is an edge of length 2. You make an intermediary node and add edges of length 1 between them. Then use the normal breadth first search. (You also need to do this for nodes of length 3 and 5, adding 2 and 4 nodes). Since you only add a O(E) nodes it's the same complexity.

Upvotes: 1

Related Questions