0

What is an efficient way to find the shortest path from one node to another node in a large graph (with around 300k nodes)?

I have tried Breadth first search and Depth first search, but they are not fast enough for my case.

I have heard about Bidirectional search, but it works only for undirected graph.

Ha An Tran
  • 337
  • 1
  • 21
  • 3
    try [A* search](https://www.geeksforgeeks.org/a-search-algorithm/) – rustyx Apr 24 '20 at 18:55
  • [This review](https://arxiv.org/pdf/1504.05140.pdf) may be helpful. – Evg Apr 24 '20 at 19:13
  • In theory, you can't beat BFS/DFS since they run in linear time. But could you please clarify whether your graphs has weights? – Juho Apr 24 '20 at 19:18
  • @Juho I have the coordinates of the nodes, so it might be useful if I want to find path with shortest distance. But in my case any path is possible (I preferred implementation time) – Ha An Tran Apr 24 '20 at 19:29

0 Answers0