Is there a better algorithm to find the shortest path in a graph?

0
votes

I'm facing a problem where I have to find the shortest path from two nodes in a graph. The graph has some caracteristics that I'm sure can lead to a better solution, as all the ones I've found and thought of 'till now are O(V+E). In particular:
-The graph is a single connected component. -The graph is not oriented and unweighted. -The nodes which arrange a simple cycle are a complete subgraph (***).

I need to find and return the minimum distance, given two nodes of the graph.

I've looked at different algorithms, for weighted and unweighted graphs: Dijkstra, Bellman-Ford, Floyd-Warshall and Breadth First Search, but I can't find an algorithm that makes use of the (***) property, which I'm quite sure is important and useful.

Thanks in advance.

1
algorithmgraphgraph-algorithmshortest-path
I don't grasp the graph topology. It sounds a bit like you're saying it's basically a linked list with the head and tail connected. But, if that were the case it would obviously require average-case (V+E) / 2 - Tatarize
What does "the nodes which arrange a simple cycle are a complete subgraph" mean? Specifically what's a "simple cycle" (rather than a cycle), and what does it mean to "arrange" one? - Paul Hankin
@PaulHankin A cycle may either refer to a closed walk (also called a tour) or more specifically to a closed walk without repeated vertices and consequently edges (also called a simple cycle). - from Wikipedia, Glossary of graph theory terms - phidotexe

1 Answers

1
votes

If the input to your problem is a graph and a single pair of vertices then you cannot hope for a solution faster than O(V + E) simply because you need to at least read the input data. However, if you have multiple (say, K) queries, then you can indeed do better than O(K*(V + E)).

If that is the case then one way of incorporating property (***) that I see is the following:

  1. If the graph is a (rooted) tree then the shortest distance between two vertices (u, v) is a path (u--w--v), where w is the least common ancestor (LCA) of u and v. There exists an algorithm that takes O(V + E) time for a certain precomputation and then O(1) time for the actual LCA queries (it is described, for example, here. Once you have the vertex w, it is then straightforward to calculate the length of the path, since it is essentially (depth(w) - depth(u)) + (depth(w) - depth(v)), where depth(x) is the depth of the vertex x in our rooted tree.

  2. In your case, the graph is not a tree, but resembles one a bit. I will give a high level idea of what seems to be possible for this case.

    Property (***) tells us that each strongly connected component is a complete subgraph, and the distances between each pair of vertices inside such a component is 1. Therefore, if we contract each strongly connected component into a single vertex then we could do something similar to the previous case.

    However, there would be a few subtleties to take care of. For example, when a path in the "contracted" tree passes a vertex, it could mean that we need to visit either one or two vertices in the original graph, depending on whether or not we need to switch the vertex before continuing along our contracted tree. But this is something that we can precompute once for each contracted vertex, and then each query can again be made to run in O(1) time, so overall for K queries we would then have O(V + E) for preprocessing and O(K) for queries, giving us total O(V + E + K) time.