Shortest path with a given condition

Question

The problem says to find the shortest way (the smallest amount of intermediary points), with given source and destination points, such that between two consecutive intermediary points there are two alternative routes. Also, all the connections between the points on the map are given.

I understood that the problem is about a graph with given edges and that i have to find the shortest path between two given nodes, but i didn't understand how to search the right path with the given condition (2 alternative paths between every two intermediary nodes). Is the BFS algorithm applicable in this case? And wich other algorithm could I also use?

Thanks in advance for help!

Answer 1

First let's look at the special condition. For each edge $p_i p_{i+1}$ in the path $P$ the has to exists an additional path that connects $p_i$ with $p_{i+1}$. This criterion is equivalent to: no edge of the path is a bridge edge.

This means that we can determine already before the actual shortest path search, which edges we are allowed to use, and which edges we are not allowed to use.

Therefore you can construct an efficient algorithms as follows:

• compute all bridge edges (e.g. with Tarjan's bridge-finding algorithm)
• remove all bridge edges from the graph
• execute any shortest path algorithm, e.g. BFS, on the remaining graph

Some additional notes, since you wrote that you want to use multiple algorithms. However these approaches will perform a lot worse than the one described above.

• of course you can also determine if an edge $p_i p_{i+1}$ is a bridge edge in other ways. E.g. remove the edge from the graph, and check if you can find a path from $p_i$ to $p_{i+1}$ with a DFS (backtracking), or with another BFS.
• Also you can use Backtracking itself to find the shortest path at the end.

Answer 2

BFS is for tree traversal just like DFS. For the shortest path algorithms that textbook commonly used are:

• Bellman Ford's Algorithm
• Dijkstra's Algorithm