Я пытаюсь сделать небольшое приложение маршрутизации общественного транспорта.

Мои данные представлены в следующей структуре:

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

Куда:

ключ dict графа является узломSubdict ключ является ребром между 2 узламизначение поддикта - вес ребра

Я использовал алгоритм find_shortest_path, описанный здесьhttps://www.python.org/doc/essays/graphs/ но это довольно медленно из-за рекурсии и не имеет поддержки весов.

Поэтому я перешел к алгоритму, описанному Давиде Эпштейном здесьhttp://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ (и даже лучшую реализацию можно найти в комментариях с использованием heapq)

Это прекрасно работает, это действительно быстро, но я получаю только лучший маршрут вместо списка всех возможных маршрутов. И вот где я застрял.

Может ли кто-нибудь помочь мне с этим, или, по крайней мере, дать направление? Я'Я не очень хорош в алгоритмах кратчайших путей графа.

Заранее спасибо!