Próbuję stworzyć małą aplikację do trasowania transportu publicznego.

Moje dane są przedstawione w następującej strukturze:

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

Gdzie:

klucz graficzny jest węzłemklucz subdict to krawędź między 2 węzłamiwartość poddyscypliny to masa krawędzi

Użyłem opisanego tutaj algorytmu find_shortest_pathhttps://www.python.org/doc/essays/graphs/ ale jest raczej powolny z powodu rekurencji i nie ma wsparcia dla wag.

Więc przeniosłem się do algorytmu opisanego tutaj przez Davide Epsteinahttp://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ (i jeszcze lepszą implementację można znaleźć tam w komentarzach przy użyciu heapq)

Działa świetnie, jest naprawdę szybki, ale otrzymuję tylko najlepszą trasę zamiast listy wszystkich możliwych tras. I tam utknąłem.

Czy ktoś mógłby mi w tym pomóc, a przynajmniej podać kierunek? Nie jestem zbyt dobry w algorytmach najkrótszych ścieżek graficznych.

Z góry dziękuję!