Hi,

As title suggest, I intend to implement a shipping simulation into a multiplayer browser game, basically calculating cheapest route from vertex A to B something like,

As there are several options for transportation, actually vertices are not as shown here but for each transportation method (Greece - Land / Greece - Railroad / Greece - Seaport / Greece - Airport) as shown below, so my estimation for vertices is around 1,000 but with many edges since it won't be based on country but regions so a country may have 6-10 regions all having vertices for transportation methods.

In this scenario, Dijkstra seems to be enough for calculating cheapest route based on weight. But the problem is weights are different for each country (or even region). For example, there may have an avalanche at Slovenia blocking railroad traffic so edge Greece-Train -> Slovenia-Train is weighted infinite or Italy may impose higher toll fare for Greeks than Slovenians. So, I need to calculate according to weights based on several factors changing like originating country, destination country and route.

My first naive implementation was using Dijkstra and caching results (actually using a graph database like OrientDB or Neo4J solely for this) , but I am not sure if it is a wise choice in performance terms.

Then, I considered Floyd-Warshall Algorithm (which is basically Dijkstra run up to n^3 times apparently) with an extension of storing path as well, not only weight matrix.

But the problem is, everytime there is a weight change in a single edge, I need to recalculate entire matrix for all countries. Didn't have chance to test but doubt it will be blazing fast.

So, my plan atm is having a "tick number" and getting route from matrix if "matrix tick number" is same, using Dijkstra if not until matrix is recreated.

After this wall of text, my question is,

Is this right approach in your opinion or what would you recommend instead if not?

Thanks in advance,

The idea behind using both Dijkstra and Floyd-Warshall is ensuring that player will get an updated result while reconstructing Floyd-Warshall matrix for all vertices.

Floyd-Warshall is supposed to eliminate the need for running Dijkstra once constructed.

Why are you classifying Dijkstra's as a single-pair search algorith? In my experience, Djikstra's is usually used to find the optimal path from all locations to a minimal-cost destination, by exploring a search space which you then "roll downhill" on.

1. At the destination D, set the cost of the destination C(D) to zero. Set the cost of all other locations to positive infinity (or some other arbitrarily excessive value).

2. Set up the edge cost function W(A,B), which gives the non-negative cost of traversing the edge directly from A to B. Directed edges work fine. Zero-cost edges are allowed.

3. For all locations L, let their new cost C'(L) be the lowest value among their current C(L) or among all adjacent locations A, C(A)+W(L,A).

4. Repeat (3) until no new lowest costs are discovered during an iteration.

To use the data, to go from any location X towards the destination D, traverse the edge from X to the lowest C(Y) among Y adjacent to X (aka "roll downhill"). This algorithm is tolerant of the data changing in-between steps. All locations in disconnected subgraphs that do not include D will have a cost of positive infinity.

When you dirty your edge costs, start re-calculating the costs to each destination. You can do one destination per tick, if you like. The strict Djikstra algorithm doesn't give you usable data in-between step-3 iterations, but neither does A*, so what the hell.

Why are you classifying Dijkstra's as a single-pair search algorith? In my experience, Djikstra's is usually used to find the optimal path from all locations to a minimal-cost destination, by exploring a search space which you then "roll downhill" on.

1. At the destination D, set the cost of the destination C(D) to zero. Set the cost of all other locations to positive infinity (or some other arbitrarily excessive value).

2. Set up the edge cost function W(A,B), which gives the non-negative cost of traversing the edge directly from A to B. Directed edges work fine. Zero-cost edges are allowed.

3. For all locations L, let their new cost C'(L) be the lowest value among their current C(L) or among all adjacent locations A, C(A)+W(L,A).

4. Repeat (3) until no new lowest costs are discovered during an iteration.

To use the data, to go from any location X towards the destination D, traverse the edge from X to the lowest C(Y) among Y adjacent to X (aka "roll downhill"). This algorithm is tolerant of the data changing in-between steps. All locations in disconnected subgraphs that do not include D will have a cost of positive infinity.

When you dirty your edge costs, start re-calculating the costs to each destination. You can do one destination per tick, if you like. The strict Djikstra algorithm doesn't give you usable data in-between step-3 iterations, but neither does A*, so what the hell.

(Assuming that I understood what you meant,)

As weights will change for each country (therefore a new graph for each country) , actually I only need to know cheapest paths from each region of country to all abroad per graph as cost of A->B is not necessarily same as B->A. In that case , apparently I can speed things up using Dijkstra in the way you described (which I hope same as the way I got )

Actuallyi I just noticed that for changes that are not imminent but expected (like country A proposes a law about transit fee for country B, which takes 24 hours to be voted) , there can be precalculated results making transition delay-free.

How I learned to stop worrying (about the relative size inefficiency) and love Dijkstra maps:

http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

That's the other thing about Dijkstra's algorithm. You don't need to have one global destination; if you have multiple destinations, then all points will simply pathfind to their local minima. Even if your minima are of different values, it still works out. It's expensive to store if you have absolutely massive maps, but if they're only moderate-sized maps, the space inefficiency more than makes up for the fact that it supports any number of actors using it.

How I learned to stop worrying (about the relative size inefficiency) and love Dijkstra maps:

http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

That's the other thing about Dijkstra's algorithm. You don't need to have one global destination; if you have multiple destinations, then all points will simply pathfind to their local minima. Even if your minima are of different values, it still works out. It's expensive to store if you have absolutely massive maps, but if they're only moderate-sized maps, the space inefficiency more than makes up for the fact that it supports any number of actors using it.

Thanks for the link. Seems they use a similar approach here @ https://people.mpi-inf.mpg.de/~funke/Papers/DIMACS06/DIMACS06.pdf as well.