How big is your 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. Here are sizes for a few input sets:

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.
 
Here are sizes for a few input sets:

|_. input |_. Europe |_. USA/CAN |_. USA (Tiger) |
| #nodes | 18 029 721 | 18 741 705 | 24 278 285 |
| #directed edges | 42 199 587 | 47 244 849 | 58 213 192 |
| #road categories | 13 | 13 | 4 |

From the given time limit it's obvious that pure Dijkstra won't do and we need to look at how other algorithms behave like A star search or an algorithm based on 'Highway hierarchies':http://algo2.iti.kit.edu/schultes/hwy/esa06HwyHierarchies.pdf

Since we chose half a second to be our execution time and the size of our problem to be about 20 million edges it's clear from our table that m log n is too slow. So pure Dijkstra won't do. We need to look at how other algorithms like A star search or one based on 'Highway hierarchies':http://algo2.iti.kit.edu/schultes/hwy/esa06HwyHierarchies.pdf behave for this problem.