CODEWITHSUNDEEP
algorithmgraphgraph-theory
Bryan
Bryan

Reputation: 1468

algorithm - shortest path from vertex a to b containing vertex v

I'm having trouble trying to figure out a shortest-path algorithm such that given a undirected unweighted graph with an start point a and end point b, every path must contain/run into the vertex v. Is it possible to get it in O(n) if the length is greater than n / 2?

I found this question but it didn't spark anything in my head. It did get me thinking about BFS but how would I know when I went through vertex v?

Can anyone point me into some direction? Thanks!

Upvotes: 0

Views: 793

Answers (1)

Ted Hopp
Ted Hopp

Reputation: 234857

Just break down the problem into two subproblems: find a path from a to v and then another path from v to b.

If there's a requirement that the overall path cannot reuse an edge or vertex, then you'll need to do something more elaborate. It's not immediately clear to me exactly what that is. One possibility is to remove the edges/vertices used in the path from a to v (except for v itself) while searching for a path from v to b. But that won't guarantee a shortest overall path, so you'd have to do some backtracking. But I suspect that there's a better approach.

Upvotes: 2

Related Questions