# (Cheapest) "Path" Finding

## Recommended Posts

Unduli    2498

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?

##### Share on other sites
HappyCoder    5052

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

##### Share on other sites
ericrrichards22    2422

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...)

##### Share on other sites
Unduli    2498

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

##### Share on other sites
Oolala    1102

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.

Edited by Oolala

##### Share on other sites
Unduli    2498

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.

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

Edited by Unduli

##### Share on other sites
ferrous    6137

No, I think you're overthinking it.  Your squiggly lines are just alternate node paths available.  You have path choices that can be taken that are of different costs, that's pretty much standard typical pathfinding.

For example Node 1, Greece has the following neighbors: 6, 2, 5air, 3air,3land, 3sea.  The fact that they are air land or sea though, doesn't really matter other than they have different costs associated with them.  The fact the map is spherical is also of no consequence, as the standard pathfinding algorithms don't care, they all just track what nodes they have already visited, and that would keep you from being in an endless loop.  Implementation wise, this just means you have pointers that can point in a circular fashion.

Edited by ferrous

##### Share on other sites
Trienco    2555

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.

##### Share on other sites
Paragon123    620

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.

Edited by Paragon123

##### Share on other sites
Unduli    2498

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?) ?

##### Share on other sites
Nypyren    12065

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

Of course. What is the point of having them if you're not going to check them?

Like Trienco says above, if you're not going to do something special with the multiple edges, such as adjust costs ("the train route between X and Y is currently unavailable due to extremely heavy snow"), you should just eliminate any edges sharing the same vertices by using the lowest cost edge.

Are you planning a path where the vehicle type must stay the same along the entire route, or where the vehicle can change at any node? If the vehicle has to stay the same, then you should use separate graphs so that you don't have to constantly discard invalid edges. Edited by Nypyren

##### Share on other sites
ferrous    6137

Heh, I assumed because it was a shipping simulation, the costs would change depending on the type of good being shipped, and therefore he would need to keep all three paths.  For example, shipping extremely heavy stuff, like cars?  Yeah, airfreight might not even be an option...

Also, I'm assuming they may want to search by shortest time, shortest cost, and again, ships and planes may only leave on certain dates, while a truck might be available every 30 minutes.   Lots of 'tricky' stuff, but really only involve making the heuristic function more complex.

Edited by ferrous

##### Share on other sites
Unduli    2498

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

Of course. What is the point of having them if you're not going to check them?

Like Trienco says above, if you're not going to do something special with the multiple edges, such as adjust costs ("the train route between X and Y is currently unavailable due to extremely heavy snow"), you should just eliminate any edges sharing the same vertices by using the lowest cost edge.

Are you planning a path where the vehicle type must stay the same along the entire route, or where the vehicle can change at any node? If the vehicle has to stay the same, then you should use separate graphs so that you don't have to constantly discard invalid edges.

What I was trying to ask was if a more elegant option is possible, apparently not :) So dust to dust, node to node. Also seems have problem with embargo or so (ie Greece may not use France territory but Poland can for example, it multiplies already more than enough paths).

And no, vehicle can change at any point. Just ofc planes are available if an airport is involved , seaport as well.

Heh, I assumed because it was a shipping simulation, the costs would change depending on the type of good being shipped, and therefore he would need to keep all three paths.  For example, shipping extremely heavy stuff, like cars?  Yeah, airfreight might not even be an option...

Also, I'm assuming they may want to search by shortest time, shortest cost, and again, ships and planes may only leave on certain dates, while a truck might be available every 30 minutes.   Lots of 'tricky' stuff, but really only involve making the heuristic function more complex.

Coincidentally , I assumed very same :) I was considering setting a base price (per kg for example) for per shipping type , otherwise seems it will get out of hand :)

And for the sake of simplicity, no time related events are involved. its only cost-wise.

##### Share on other sites
Oolala    1102

There are simpler ways to do it than checking everything, but they trade tons of memory for their performance, just like your proposed solution in your original topic post would.  If you store partial solutions, you do so with the use of some sort of table, and you trade the memory for storing that table to save the time it would take to generate the solution at run-time.  If you find there are certain nodes that you always take for a given solution, then some sort of table might help.  If you can't really tell up-front whether or not an edge will be part of a solution, then you're pretty much stuck because the table size grows exponentially.

Whether or not taking shortcuts will be useful depends an awful lot on your graphs topology & your edge weights.

For example, if air transit costs 1/100000th per mile as boat transit, and boat transit costs 1/100000th per mile as truck transit, then you can simplify your search a whole lot.  You can do this because you already pretty much know that you take trucks to either airports or seaports, and only chose a seaport if there isn't a reachable airport.  Your graph becomes mostly hierarchical at that point.  Your 'simplification' could then pretty much keep a table of place pairs, A and B, describing that place A and B are nearer to each other than the sum of the distance between A and an airport and B and an airport.  Since you know, because of the massive cost bias mentioned earlier, that this is the only situation in which you wouldn't use an airport, you can use your table to rule stuff out quickly.  You'd further use the knowledge that there are more airports than non-airports, and thus a table like this is actually cost-saving.  Your table also wouldn't blow up because you'll have a roughly constant number of places nearer to any given location than the nearest airport.

Check the table, if you find an entry then you run A* on truck roads, otherwise you run for A to it's nearest airport, then the airport search to get to B's nearest airport.

This is of course an unfair simplification, but you get the idea.  If you have domain knowledge, you can simplify stuff substantially.  This simplification comes not necessarily at making the problem easier, but leveraging domain knowledge to develop better A* heuristics and to adjust the graph topology from a naive solution.  If you don't have domain knowledge, then you either write your program to discover knowledge, or you go with a general solution that doesn't require knowledge.  Either way though, this is a wholly traditional search problem, and we're only talking the degree of knowledge you have regarding the topology of the graph.

Should be noted that A* pretty much requires some degree of domain knowledge for heuristic authorship, otherwise it just degrades into BFS which is absurdly ineffective on large graphs.

##### Share on other sites
ankhd    2304

Hello heres a A* made easy

##### Share on other sites
Unduli    2498

I just found out Neo4J , anyone experienced shortest path performance of graph databases? (which i assume their purpose)

##### Share on other sites
hossainiir    1044

Hi,take a look to this, it shows you different path finding methods with different heuristic methods, also the source code is here.

I'm using A* with chebyshev heuristic method, I think this is faster and cheaper than the others.

Edited by hossainiir

##### Share on other sites
Unduli    2498

Hi,take a look to this, it shows you different path finding methods with different heuristic methods, also the source code is here.

I'm using A* with chebyshev heuristic method, I think this is faster and cheaper than the others.

As there are several factors to be taken into consideration, I favor neo4j atm if performance is satisfactory.