유향 그래프에서 하나의 정점에서 다른 정점으로의 최단 경로

Question

내 그래프가 방향이 지정되고 매우 큽니다. 그래프의 꼭짓점은 마을을 나타내고 가장자리는 마을에서 마을까지의 버스 여행 경로를 나타냅니다. 목표는 하나의 정점에서 다른 정점으로의 경로를 찾는 것입니다. 알고리즘이 버스 간의 전송 시간을 고려하는 것이 매우 중요합니다.

나는 Dijkstra의 알고리즘을 사용 하겠지만 전체 그래프에서 하나의 방법을 찾습니다. 버텍스에서 버텍스까지 "최상의"방법을 찾아야합니다. "최고"라는 말은 가장 짧은 전송 시간을 의미하지만, 이것이 가장 중요한 포인트는 아닙니다.

Answer 1

버스를 변경하기위한 "전송 시간"은 중요한 변수이며 그래프에서 여분의 꼭지점으로 표현하는 것이 가장 쉽습니다. 가장자리의 가중치를 버스 간 이동 시간으로 가정하면 노드와 에지를 사용하여 두 버스 간의 전송 시간을 나타낼 수도 있습니다.

Answer 2

이동 기간은 확실하지 않지만 시간에 따라 달라지는 고속도로 계층 구조 작업은 goldberg, sanders 등 많은 사람들이 수행합니다. Google (dblp 또는 과학적 e-lib)에서 검색 할 수 있습니다. 대륙 크기의 정적 데이터 세트의 경우 수천 시간이 더 소요되며 동적 시나리오와 정적 시나리오 모두에 적합합니다.

Answer 3

하나 이상의 최단 경로를 찾으려면 this question을 참조하십시오.