Is there an efficient way to find shortest paths in a functional graph?

user_14011933 0
Viewed 148

My task is to process Q shortest path queries in a functional graph with V nodes. Q and V are integers that can be up to 100000.

My first idea was to use the Floyd-Warshall algorithm to answer queries efficiently, but this algorithm takes O(V^3) time to calculate the shortest paths, which is way too slow.

My second idea runs in O(QV) time, because for every query I start at the starting node and traverse through the graph until I discover a cycle or reach the destination node.

However, this solution is still too slow; it has no chance of quickly processing queries when V and Q become large. I think that there is some pre-processing or another technique that I could use to solve this, but I haven't been able to find any online resources to help guide me. Can somebody please help me out?

shortest-path graph-theory algorithm
2 Answers

A functional graph means that each node has only a single out-edge, so the maximum number of steps between A and B couldn't be more than the number of vertices without encountering a cycle. You should be O(V).

Since there are no choices, you could readily build a CostMap[V][V] which recorded the distance between two nodes, and lazily fill it as you encounter queries; thus successive queries would approach constant time.

user_46644150

There are a a lot of algorithm designed for this purpose, you can look up the Depth First Search (DFS) or Breadth First Search (BFS) algorithm. As well as the Djikstra's algorithm and the A* (A star) algorithm, this last one is often used in pathfinding for video games. They all have their pros and cons and it depends on the architecture of your network but it should suit your needs.

user_127585510
Related