La verdad es que la mayoría de la gente utiliza una variación personalizada del A* algoritmo. Esto lo verás en la mayoría de los "grandes" (no puedo decir quiénes son en un foro público, pero te puedo decir que probablemente utilices uno de ellos - garantizado), donde la modificación de la heurística es muy dependiente de los conjuntos de datos que utilizan.
Usted mencionó pgrouting ya, que yo consideraría una opción "tradicional". Es bueno para hacer algoritmos de enrutamiento simples y para la mayoría de los problemas. También es fácil de usar y utiliza una base de datos tradicional en su backend.
Sin embargo, depende realmente de la escala y el tipo de problema que se intente resolver y el enrutamiento es un gráfico problema.
Una vez más, los "grandes" suelen tener muchos datos asociados a su gráfico (por ejemplo, datos de tráfico, rutas de autobús, recorridos a pie) que afectan al algoritmo de enrutamiento. Estos se conocen como planificadores de viajes multimodales (en los que también se puede elegir el "modo" de planificación -sin carril bici, sólo con transporte público-, ese tipo de cosas). Se puede pensar que la planificación de viajes también se convierte en una cuestión de tiempo (por ejemplo, si se camina volver unos bordes atrás, podrá coger el metro que le lleve a su destino adelante mucho más rápido que si sólo se tratara de navegar por los bordes hacia delante utilizando el coste más bajo).
Los "grandes" no almacenan sus datos en una base de datos tradicional propiamente dicha, sino que utilizan gráficos precalculados (¡bienvenidos los clusters de hadoop/mapreduce!). Como puedes imaginar, estos grafos llegan a ser realmente grandes, por lo que saber cómo conectar las aristas de los grafos adyacentes puede ser un reto.
De todos modos, te recomendaría que miraras algunos proyectos de gráficos de enrutamiento multimodal:
Servidor de gráficos me viene a la mente. No hay mucha documentación, pero sí un montón de genialidades de codificación (AFAIK, creo que MapQuest utiliza una variación de este proyecto para algunos de sus productos de enrutamiento).
Otra opción sería el OpenTripPlanner que tiene un montón de gente inteligente detrás (incluyendo gente de graphserver).
