# Path uniqueness in undirected graph

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.

• Are you interested in simple paths? Jun 12, 2020 at 16:56
• Yes, only simple paths. Jun 12, 2020 at 18:27

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$$.