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!

  • $\begingroup$ Also, you say "the problem requires two different algorithms". What does this mean? $\endgroup$ – dkaeae May 23 at 15:06
  • $\begingroup$ Hello! It means that the problem should be implemented with two diffrent types of algorithms like dinamic programing, Greedy, Backtracking.... $\endgroup$ – John May 23 at 15:10
  • 1
    $\begingroup$ Is this homework? If so, see here for tips on asking questions about exercise problems. $\endgroup$ – dkaeae May 23 at 15:11
  • $\begingroup$ I've edited it. $\endgroup$ – John May 23 at 15:51
  • $\begingroup$ I'm not understanding the condition completely. Is it "such that between ANY two consecutive intermediary points there are two alternative routes" or "between AT MOST ONE PAIR OF consecutive intermediary points"? In any case I would advice thinking about Strongly connected components. And I'm guessing that "two alternative routes" means, that the second route can be a lot longer than the first (of size 1). Otherwise this means that it is just a multi-edge. Am I right? $\endgroup$ – Jakube May 24 at 21:13

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.

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
  • $\begingroup$ BFS is also a valid algorithm for finding the shortest path. Since the shortest path between two nodes in an undirected graph is exactly the path between the root and another nodes in the BFS traversal tree. Also I don't think that your post answers the question, since you don't discuss the special condition at all. $\endgroup$ – Jakube May 24 at 21:06
  • $\begingroup$ You are right but you need to modify the BFS to find the shortest path. $\endgroup$ – JustinC May 30 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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