CODEWITHSUNDEEP
pythonalgorithmgraphdijkstra
Joe
Joe

Reputation: 279

Finding overall shortest path on dense graph

Say you are a package delivery company with a fixed start location on a map. You have to deliver 40 packages but have unlimited drivers, unlimited gas, and the only constraints are that you want to put the least amount of miles on the vehicles total and each vehicle can hold 16 packages. The trucks can go 18 mph and start at 8am

At some point in the delivery schedule one package will be re-assigned an address.

I know that Dijkstra's algorithm allows us to find the shortest path between two points, But I cant think of a valid way in which I could apply the algorithm to 3 separate paths that have the ability to change in route and still maintain the lowest possible miles.

I'm probably overthinking it but could someone point me in the right direction?

Upvotes: 2

Views: 208

Answers (1)

templatetypedef
templatetypedef

Reputation: 372714

This problem is unfortunately NP-hard, meaning that as of now we don’t have any algorithms for it that are known to be worst-case efficient, deterministic, and always correct. That is, we don’t have something like Dijkstra’s algorithm or A* that we can just pull off the shelf and guarantee to get a fast optimal result from.

That being said, this is a problem we do actually want to solve on a regular basis (see, for example, this article about UPS). You may want to consider using an integer programming solver, which isn’t guaranteed to run efficiently but which in practice often does.

Upvotes: 1

Related Questions