How fast do you want your code to be? seconds? hundreds of milliseconds?

Usually people feel something on the web is fast if it takes less then half a second to execute. So let's say half a second.

A response on the web feels fast if it takes less then 500 milliseconds. So let's pick half a second.

How big is your graph? Do you want to solve the problem for a city, a coutry or even a continent?

How big is the graph? Do you want to solve the problem for a city, a coutry or even a continent?

Each is about a magnitude larger than the other and may mean you need different approaches. Let's say we want to solve it for the whole of Europe.

Each is about a magnitude larger than the other and will be solved by different approaches. Let's say we want to solve the problem for the whole of Europe.

Here are sizes for a few input sets: