I've only played around with Neo4j, but it looks like Neo4j 3.0 could handle your node and edge count (although not earlier versions). Your app likely would ha

I've only played around with Neo4j, but it looks like Neo4j 3.0 could handle your node and edge count (although not earlier versions). Your app likely would have been easier to write with python/Neo4j than python/SQLite due to Neo4j's query language (incidentally, Neo4j also prefers to use bidirectional BFS for shortest path, and executing the search is a very simple query similar to an SQL query). Neo4j would possibly perform better as well (I'm not sure about that, given SQLite is pretty optimized for reads). However, as the neighboring comment states, Neo4j is quite resource-intensive. It wouldn't work on any kind of micro instance, I'm pretty sure.