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.