CODEWITHSUNDEEP
c++boostgraphpathshortest-path
petuh666
petuh666

Reputation: 11

boost shortest path finding algorithm

Good day, dear friends.

I want to find shortest path in random graph. I use boost graph library. As I understand I need to build graph using existing distances between dots. After that I need to use some algorithm...

As I see Dijkstra's algorithm is really finds all paths from 1 point to others. (It should be slow?)

A* wants some additional data (not only distances)

How can I find the shortest path between 2 points? I saw many shortest path algorithms headers in bgl folder, but I didn't find examples how to use them.

Also I can precompute something for graph is needed.

What should I do?

Upvotes: 0

Views: 946

Answers (2)

Iman Mirzadeh
Iman Mirzadeh

Reputation: 13550

it depends on how many nodes you have , as you mentioned your nodes are around O(10^4) and edges are O(10^4) which is good
so in BOOST LIBRARY DOCS it sasy The time complexity is O(V log V + E). so if you put V = 10^4 and E = 10^4 you get about O(10^5) which is very good and can run less than 1 second on a normal computer so you can use it.

A* Algorithm can run faster than Dijkstra but it needs a heuristic function which must be monotonic and admissible and it might be hard to find that function depending on your problem.

so i think Dijkstra would be good enough for your case

Upvotes: 1

Apurv
Apurv

Reputation: 32

Dijkstra's algorithm takes O(E log(n)) time - where E = #edges and N=#nodes. It should be fast enough. Please comment on approximate values of E and N.

In some cases (e.g. a Social graph), the following is faster: - assuming edge weights are 1, N is very large, degree of nodes is small (few hundreds): Do a 2 level BFS from node1, 2 level BFS from node2 and intersect the sets. If there's a path length of <= 4, you'll find it.

Upvotes: 1

Related Questions