Estou tentando fazer um pequeno aplicativo de roteamento de transporte público.

Meus dados são representados em uma estrutura a seguir:

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

Onde:

grafo chave dict é um nósubdict key é uma aresta entre 2 nósvalor de subdivisão é um peso de borda

Eu estava usando o algoritmo find_shortest_path descrito aquihttps://www.python.org/doc/essays/graphs/ mas é bastante lento por causa da recursão e não tem suporte de pesos.

Então eu mudei para o algoritmo descrito por Davide Epstein aquihttp://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ (e uma implementação ainda melhor pode ser encontrada nos comentários com o uso do heapq)

Funciona muito bem, é muito rápido, mas eu só obtenho a melhor rota em vez da lista de todas as rotas possíveis. E é aí que eu fiquei.

Alguém poderia me ajudar com isso, por favor, ou pelo menos dar uma direção? Eu não sou muito bom em algoritmos de caminhos mais curtos.

Desde já, obrigado!