CODEWITHSUNDEEP
algorithmdata-structuresnodesgraph-theory
eli.rodriguez
eli.rodriguez

Reputation: 490

How to improve several shortest paths search over the same graph ?

I had the next situation and i need to find the best optimization to solve the problem.

I graph G

for putting an example lets asume the graph looks like this enter image description here

And the problem require find the addition of the weights in shortest paths (just lets call it SP) between several vertices and add them all.

I mean if the shortest paths between a - b is a -> c -> d his SP would be x0 + x1 + x2

So a set of my problem would look like this:

So the naive solution is to found the SP for between every set every time

SP(a,g) + SP(a,h) + SP(e,f) + ... = result

So this is when the optimization task begin , i already implement two improvements but i need the best optimization (if it is possible), let see what i already did:

  1. Save every result of every shortest path found so if there is asked again i had the problem

example. if the SP between a - g is w i save it so if i asked again which is the value of SP between a - g or g - a i already know the result

  1. Save every subsequent SP found and save it

example.

If i asked to found the SP between a - g. Lets assume that the shortest paths between that two vertices is a -> c -> d -> j -> g so the SP would be

x0 + x1 + x2 + x3

so i can save a - g but also i can save the SP of all the subsequent paths found.

for example the shortest paths between a and j is a -> c -> d -> j or the paths between c and j is c -> d -> j

here are all the SP founds

SP(a,c) = x0
SP(a,d) = x0 + x1
SP(a,j) = x0 + + x1 + x2

SP(c,d) = x1
SP(c,j) = x1 + x2
SP(c,g) = x1 + x2 + x3

SP(d,j) = x2
SP(d,g) = x2 + x3

SP(j,g) = x3

And i save every result.

So now this last improvement has save a lot time but it seems don't enough since the quantity of nodes and the set of the SP to found is considerable big.

So any suggestion or any particular algorithms that i can use to improve this problems (i hope been enough clear please write a comment if any details is not explained) ?

Upvotes: 0

Views: 81

Answers (2)

Jerry Federspiel
Jerry Federspiel

Reputation: 1524

If you have many pairs to compute, consider Floyd-Warshall; it will give you the shortest-path distance from any point to any other point (at the cost of O(n^3) runtime).

Upvotes: 1

xuhdev
xuhdev

Reputation: 9333

You can use Dijustra to search for the shortest path between one node and all other nodes, and cache all the length of the shortest paths using a Hash table.

Then, for a given set of pairs of nodes, you can quickly extract the path length from the Hash table.

Upvotes: 1

Related Questions