CODEWITHSUNDEEP
javagraph
emilly
emilly

Reputation: 10530

Dijkstra algorithm to find shortest path between two nodes in big graph?

Dijkstra Algorithm says

For a given source node in the graph, the algorithm finds the shortest path between that node and every other

I got the algorithm to find the shortest path between that node and every other. But my question if I need to find the shortest path b/w two specic node(say N1 and N2) for big graph like Linkedin/facebook do I need to calculate the distance between that node N1 and every other Node(user which means billion of users) on linkedin first, store it in cache memory and then return it from cache whenever shortest distance b/w two nodes is asked ?
Is dijkstra algorithm performs better there or any other algorithm like BFS better makes sense there ?

I came across similar question Java - Find shortest path between 2 points in a distance weighted map but this question refers the very small sample set and uses the dijkstra algorithm here.

Upvotes: 2

Views: 1289

Answers (1)

Roee Gavirel
Roee Gavirel

Reputation: 19453

I agree that Dijkstra Algorithm is not the best option for this kind of problem. Since you don't have weights, I don't see any reason why you should complicate the solution. A simple BFS would be perfect for you, and it would be optimal.

Upvotes: 0

Related Questions