1
$\begingroup$

Let's consider an undirected graph with two special vertices: start and finish. The graph is relatively sparse. The edge count is expected to be three times or four times higher than the vertex count.

I am looking for an algorithm that decides whether there exists some path between start and finish and if it is unique. The output of the algorithm is one of the three possible answers:

  • There is no path between start and finish.
  • There is exactly one path between start and finish.
  • There are two or more paths between start and finish. The two paths need not be disjoint. They just must not be identical.

Currently, I have the following algorithm implemented: I run breadth-first search from start vertex to find the shortest path from start to finish. If the finish vertex is unreachable, I am done. If I find a path, I iterate over its vertices except start and finish. I remove the vertex and run BFS from start vertex again. If the finish vertex can be reached, I am done as I have found another path from start to finish. If the finish vertex is unreachable, I undo the vertex removal and continue with another vertex. If the finish vertex is always unreachable during this loop, the initial path is unique.

I wonder if there is some more efficient algorithm than running BFS for each vertex of the initial path.

EDIT: As mentioned in the comment, I am interested only in simple paths, i.e. paths without repeating vertices.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Are you interested in simple paths? $\endgroup$
    – Steven
    Jun 12, 2020 at 16:56
  • $\begingroup$ Yes, only simple paths. $\endgroup$
    – Cimlman
    Jun 12, 2020 at 18:27

1 Answer 1

Reset to default
3
$\begingroup$

I am assuming that you are interested in simple paths only. Otherwise the answer is trivial.

You can solve your problem in time $O(n)$. Let $s$ be your start vertex and $t$ be your target vertex. Consider the graph as weighted where every edge has weight $0$.

Find any path $P$ from $s$ to $t$ in $G$. This takes time $O(n)$. If $P$ does not exist then there is no path from $s$ to $t$. Otherwise set the weight of each edge in $P$ to $1$ and find a shortest path $P'$ in the modified graph. This takes time $O(n)$ using a straightforward modification of Dijkstra's algorithm.

If $P' = P$ then there is a single path from $s$ to $t$ in $G$. Otherwise there are at least two distinct paths from $s$ to $t$ in $G$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I would say that your algorithm does not solve the problem. As stated in the enumeration of three possible results in my question, the paths need not be edge disjoint. I need to find out whether the initially found path is the only possible path from start to target. $\endgroup$
    – Cimlman
    Jun 12, 2020 at 16:29
  • $\begingroup$ Sorry, I had misinterpreted your question. See my edited answer. $\endgroup$
    – Steven
    Jun 12, 2020 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.