Python Dijkstra k кратчайшие пути

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

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

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

Где:

  • graph dict key - это node
  • subdict key - это ребро между двумя узлами
  • Значение subdict - это вес кромки

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

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

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

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

Спасибо заранее!

Ответы

Ответ 1

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

Алгоритм

  • Запустите алгоритм Дейкстры из начальной точки и получите список disS [i] (кратчайшее расстояние между начальной точкой и точкой i). А затем запустите алгоритм Дейкстры из конечной точки и получите список disT [i] (кратчайшее расстояние между конечной точкой и точкой i)
  • Создайте новый график: для края в исходном графе, если disS [a] + disT [b] + w (a, b) == disS [конечная точка], мы добавляем ребро в новый граф. Очевидно, что новый график представляет собой DAG (Directized ациклический граф) и имеет приемник (начальную точку) и целевую (конечную точку). Любой путь от приемника до цели будет самым коротким путем в исходном графе.
  • Вы можете запустить DFS в новом графике. Сохраните информацию о пути в рекурсии и возврата, когда вы достигнете цели, сохраненные информация будет одним кратчайшим путем. Когда окончание алгоритма зависит от вас.

Псевдокод:

def find_one_shortest_path(graph, now, target, path_info):
    if now == target:
        print path_info
        return
    for each neighbor_point of graph[now]:
        path_info.append(neighbor_point) 
        find_one_shortest_path(graph, neighbor_point, target, path_info) #recursion
        path_info.pop(-1) #backtracking

def all_shortest_paths(graph, starting_point, ending_point):
    disS = [] # shortest path from S
    disT = [] # shortest path from T
    new_graph = []
    disS = Dijkstra(graph, starting_point)
    disT = Dijkstra(graph, endinng_point)
    for each edge<a, b> in graph:
        if disS[a] + w<a, b> + disT[b] == disS[ending_point]:
            new_graph.add(<a, b>)
    find_one_shortest_path(new_graph, starting_point, ending_point, [])

Ответ 2

В Networkx есть функция, чтобы сделать это all_shortest_paths.

Он возвращает генератор всех кратчайших путей.