A * 그래프를 가져 오는 알고리즘

Question

나는 최단 경로를 찾기 위해 최단 경로 알고리즘이 필요한 프로젝트에서 작업하고 있습니다. 현재 David Eppstein의 Dijkstra 알고리즘 구현을 사용하고 있지만 그래프의 특성 (약 360 만 노드)으로 인해이 최단 경로를 찾는 데 거의 1 분이 걸릴 수 있습니다. 나는 A * 알고리즘이 더 빠르게 실행된다는 것을 알고 있지만 모든 구현은 그리드 스타일 대 그래프 스타일을 기반으로합니다. 그래프의 예는 다음과 같습니다 :

graph = {"A": {"B": 2} 
    "B": {"A": 2, "C": 5, "D": 4} 
    "C": {"B": 5, "E": 7} 
    "D": {"B": 4, "E": 10} 
    "E": {"C": 7, "D": 10} 
    } 

이런 종류의 그래프를 입력으로 받아들이려면 A *를 구현 한 일부 온라인 코드를 알고있는 사람이라면 알려 주시기 바랍니다.

Answer 1

모든 일반적인 shortest path 알고리즘이 구현 된 NetworkX 이라는 파이썬 그래프 라이브러리가 있습니다.