0

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!

Community
  • 1
  • 1
Bryan
  • 1,438
  • 3
  • 15
  • 24
  • 2
    Just find a path from a to v and then another path from v to b. – Ted Hopp Sep 14 '14 at 01:38
  • Restate your question clearer. Not sure what you are asking. Also note that you said "unweighted", there is no such thing as shortest path if the graph is "unweighted" – smac89 Sep 14 '14 at 01:40
  • 1
    @Smac89 - Of course there is. Unweighted simply means that all edges have equal weight. So shortest path for an unweighted graph is a path with the smallest number of edges. If you _must_ have a weight for an algorithm to work, by convention the weights are all 1. – Ted Hopp Sep 14 '14 at 01:43
  • I see. OP should look into connected components algorithm: http://en.wikipedia.org/wiki/Connected_component_(graph_theory) – smac89 Sep 14 '14 at 01:47
  • 2
    When you say "path" do you allow repeated vertices or edges? If yes, then the answer from @TedHopp is correct. If not, then you need something cleverer. – Paul Hankin Sep 14 '14 at 01:54
  • @Anonymous - Good point. Of course, if no repeated edges and/or vertices is a requirement, then there may not be such a path, even for a connected graph. (E.g., any graph where v is distinct from a and b and has degree 1.) – Ted Hopp Sep 14 '14 at 02:00
  • @Anonymous if `v` is connected to `G-{v}` with one edge only, there won't be any answer with that additional restriction. Which shows, again, that we don't have enough information... – Nir Alfasi Sep 14 '14 at 02:14
  • Thanks all. Everything you all wrote makes sense and I was definitely overthinking this. @TedHopp, if you want to write an answer, I'll rep it and mark it as an answer. – Bryan Sep 14 '14 at 02:21

1 Answers1

2

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.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521