Estoy tratando de hacer una pequeña aplicación de enrutamiento de transporte público.

Mis datos están representados en la siguiente estructura:

graph = {'A': {'B':3, 'C':5},
     'B': {'C':2, 'D':2},
     'C': {'D':1},
     'D': {'C':3},
     'E': {'F':8},
     'F': {'C':2}}

Dónde:

graficar dict key es un nodoLa clave de subdicto es un borde entre 2 nodosvalor de subdicto es un peso de borde

Estaba usando el algoritmo find_shortest_path descrito aquíhttps://www.python.org/doc/essays/graphs/ pero es bastante lento debido a la recursión y no tiene soporte de pesos.

Así que me mudé al algoritmo descrito por Davide Epstein aquíhttp://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ (e incluso una mejor implementación se puede encontrar allí en los comentarios con el uso de heapq)

Funciona muy bien, es muy rápido, pero solo obtengo la mejor ruta en lugar de la lista de todas las rutas posibles. Y ahí es donde me pegué.

¿Podría alguien ayudarme con eso por favor, o al menos dar una dirección? No soy muy bueno en los algoritmos de trayectos más cortos.

¡Gracias por adelantado!