pgRouting

pgRouting adds network-analysis algorithms to a PostGIS database: Dijkstra and A* shortest paths (including bi-directional variants), K shortest paths, Johnson and Floyd-Warshall, the travelling salesman problem and turn-restricted shortest paths. Because each edge cost is computed in an SQL query, it can be changed dynamically – by travel time, road class or a closed link – and results reflect the current data immediately. Suited to transport engineers, logistics planners and analysts of infrastructure networks. Limitations: it is not a standalone program – it needs PostgreSQL and PostGIS plus SQL skills, and preparing a clean network layer (topology) is the user's job.