Is a graph database better for shortest paths algorithms?

You certainly dont have to reinvent the wheel if you are using any graph database, like Neo4j. Many shortest path algorithms are built into this and it's designed to handle complexity in case you have to consider speed limitation in any specific road, one-way road, score of a road etc. How do you keep up with performance when your data grows 10 times, or, 100 times. Considering your total computation time 3sec for 100,000 ways, it can be in minutes for 1M ways and in Neo4j, the response will be in milli sec.

The breakthrough with graph databases is not only performances, it more about concept: your routing algorithms deal with single relational graphs (that is graph were links are all of the same type) whereas with graphdatabases you have a multi-relational graph.

This enables you to compute the shortest path between nodes taking only a specific kind of edge or avoid another type.

For more information you should read about the algebra behind graph db and the concept of pipes.

I strongly recommend thinkerpop project to start with graph database.

I don't have experience with "graph" databases but judging by your question i have a few things in mind.

First of all, the straightforward answer will be "Create such a graph database and do a performance comparison with your solution". You could measure memory usage, execution time (speed), cpu utilization and/or possibly other metrics. That would provide you with enough data to make your decision.

My other advice is to revise your method. The three problem properties that you described (one table, loading all paths & no need for scalability) apply in your current domain but not in the graph databases' one. It's a whole different programming paradigm and you might have to adjust and adapt your method to suit the domain of those special kind of databases. It is unreasonable to do performance or any other kind of comparisons if you're applying your standard approach in a non-standard environment (like that graph database).

Recap: Translate your problem to the terms of the graph database and model it accordingly. After doing that, do a performance comparison between the two solutions.

My bet is, assuming that you translated & modeled your problem suitably for the graph database, it will grant you better performance. Your classical approach of "store-read-sort" is simple but not that effective unless optimized aggressively.