Hello there,

Well, my question is not of classic "pathfinding" ones, at least not sort of.

For a shipping simulation (browser based), I need an effective way to calculate cheapest path. Cheapest path means a combination of plane - truck - ship to send something world wide.

For example from Ireland to Greece, you can either

- ship from Ireland to France then France to Greece by truck

- can use ship whole route

- can directly send by plane

- can send to France first then by plane etc etc.

Cost of transportation methods differ to distance and type obviously, but there is also alternative routes (like an embargo to France can't use that route)

In that case ,

I doubt calculating route each time is wise, and possibilities are too much for an automated table, so I consider something between them, a route will be added to table if someone prefers then will fetch from table for future uses.

But wonder if there is a better option or a flaw?

Thanks in advance.

When actually finding the path, you can use http://en.wikipedia.org/wiki/Dijkstra's_algorithm

The edge length can be whatever metrics you want, such as cost or distance.

If routes never change, I would have all of the routes calculated. The number of paths between cities is only n^2 where n is the number of cities. if all of the paths are bidirectional then the amount of paths is cut in half. If you look at the numbers it isn't too bad for values in the hundreds or less. Lets look at a lookup table with 200 cities. The number of routes is 200x200 or 40,000. If each route takes on average n/2 hops between cities, which is the worst case if all cities were in a straight line and each step in the route takes two bytes to store, that is about 200 bytes per route. So the total amount of memory used to store all routes between the 200 cities is 40,000 routes * 200 bytes per route would be about 8 megabytes. 8 megabytes is easily manageable,

If you budget around 2 gigabytes to storing the table, you can store up to 1,200 cities still using the worse case of n/2 average hops per route. If the average number of hops is 10, you can store all of the routes between 14,000 cities in 2gb. A database of this size could fit in ram, however as this database gets larger you would want to store the database on the disk and cache frequently used routes in ram

I think you want to look into dynamic programming.

Cormen's Introduction to Algorithms is pretty solid on this, and a ton of other algorithmic stuff as well. There are a couple, three chapters on different graph search algorithms, as well, if that ends up being more useful.

(I'm not totally sure about the legality of the pdf that I linked, but it is the 3rd google search result for the book...)

Doubt I possess math skills regarding graph search, but still thank you.

Maybe a simplification is needed as simulation includes other variables, making it rather complex

Well, my question is not of classic "pathfinding" ones, at least not sort of.

Actually, it is entirely a classic "pathfinding" problem. All of the literature on pathfinding pertains exactly to your problem. The solution you proposed in your original post is a well established solution for systems with a large number of queries that are small enough for computation.

Anything you read or look at regarding pathfinding pertains to your problem.

Sorry for late reply.

I am no way near expert on subject but I tend to believe though this is a pathfinding problem but its not so classic.

I checked some pathfinding algorithms @

http://qiao.github.io/PathFinding.js/visual/

and

http://buildnewgames.com/astar/

First,

World is ofc spherical so no edges of map, have no idea how to implement it. (also doubt if it is still 2D)

Then,

In these examples, a tile is either passable or not ( 0 or 1 )

but I have to implement (sorry for ruining Dijkstra animation)

from a happy world each node links to other only once

to this mess

Each country/city can be connected to other one directly up to 3 ways.

So have no idea what to do

If your algorithm is looking for the cheapest route, there is absolutely no point to even have more than one connection between any two nodes, because there should never be any reason to NOT always pick the cheapest one. It's just pointlessly inflating your search space and making things look more complicated than they are.

Is it a game where players first need to establish these routes? Even then, as soon as a player establishes a new type of connection between two places, only the cheapest one should be kept.

You mention things like embargos and I'll assume they are dynamic events and not always in place. Still, in your example it has nothing to do with the connections, only with the nodes. No point in considering multiple ways to get to France, if you can't get there at all.

Another factor would be if your simulation also considers the cost for moving freight between transports. If moving everything from a truck to a ship costs extra, this cost might outweigh the benefit of using the ship. Now you do need all connections.

How you manage your graph and how best to search depends on your requirements.

As far as algorithms go, A* is just like Dijkstra with the addition of estimating the remaining cost from a new location to the destination. This could still make sense if it's a reasonable assumption that a location closer to the destination will be cheaper than one further away. But since the difference in implementation is pretty trivial, I'd probably start with Dijkstra and try changing to A* only if it isn't fast enough.

You are confusing "shortest distance" for "best route" calculated in classic pathfinding.

In classic path finding all you are doing is finding the path from node A to B with the lowest weight, the weight is generally expressed as distance in articals/tutorials because it is easy to visualize.. but can just as easily be monetary cost or even arbitrary random (non negative) values... so your problem is exactly the same as any other path finding algorithm.

You don't even have to worry about multiple paths between the same two nodes... where you currently have Land/Sea/Air from greece to france... replace greece with Greece(airport)/Greece(Seaport), Greece(train station) and replace France with France (airport), France(Seaport), France(train station). Of course, your graph doesn't even need to be physically representative of any geography... the numbers don't care if they are abstract or concrete.

Finally 2D/3D/4D doesn't matter, the only thing that matters is that there are a set of nodes connected by edges and that each edge has a scalar (non negative) weight, this is why graph theory deals with nodes and edges rather than points and vectors.

Thanks for clarifying but,

Do I have to check all of Greece(airport) / Greece(seaport) / Greece(train) in that case (ie 3 search?) ?