CODEWITHSUNDEEP
algorithmgraphgraph-theory
chuck183
chuck183

Reputation: 3

Finding a specific edge in an undirected graph between two vertices

I'm trying to write an abstract algorithm using graph theory.

Given an undirected and unweighted graph G=(V,E), two vertices: m,n∈V and a specific edge e∈E. I want to check if edge e is a part of all the shortest paths between m and n.

My algorithm:

  1. do BFS scan from m until reach to n. \\ O(V+E)
  2. int temp <-- d[n] \\ O(1)
  3. boolean ret \\ O(1)
  4. take out edge e from G. \\ O(1)

  5. do BFS scan from m until reach to n \\ O(V+E)

    • if d[n] = ∞, ret <-- true
    • if d[n] == temp, ret <-- false
    • if d[n] > temp, ret <-- true

  6. return edge e into G. \\ O(1)

  7. return ret

Time Complexity analysis: O(V+E)

Memory analysis: extra O(2) for temp and ret.

What do you say? Is it correct, or you have a better idea with less time complexity?

Upvotes: 0

Views: 308

Answers (2)

lPlant
lPlant

Reputation: 153

It would not be O(V+E). The worst case in a breadth first search is that every edge has been searched, at which point if the node has not been found then the search fails. This gives this section a complexity of O(|E|), since this is the dominant calculation, all others O(1), the complexity is O(|E|).

Upvotes: 1

amit
amit

Reputation: 178451

Your algorithm seems correct, and will indeed find if e is participating in all unweighted-shortest paths.

Proof:

  • If e is in all shortest paths -> removing e will negate all this paths -> the new shortest path will be longer than the old one -> the algorithm yields the correct answer.
  • If e is not participating in some shortest path (let it be p) -> by removing e, the path p remains, and thus the shortest distance from m to n remains the same -> The algorithm yields the correct answer.

However, your memory analysis is wrong.

BFS requires O(V) extra space, for a visited set - so the extra space is O(V)

Upvotes: 0

Related Questions