나는 Diskjstra의 대체품으로 의도 된 BFS 기반 경로 찾기 알고리즘을 생각해 냈습니다. (솔직히 다른 사람이 과거에 그것을 생각해 냈습니다. 어디서나 온라인으로 언급 할 수는 없습니다.) 나는 달리기 시간이 무엇인지 알아 내려고 노력하고 있지만, 친구들과 나는 그것에 대해 토론하고 결정적인 답을 찾을 수 없었다. 다음은 Go의 알고리즘에 대한 설명과 구현에 대한 링크입니다. 실행 시간이 e + e^2 + e^4 + ... + e^2d 인 것으로 생각됩니다. 여기서 e는입니다. 버텍스 당 평균 에지 수와 d는 최종 최단 경로 (O (e^2d))의 거리입니다. 문제는, 이것은 내 친구가 지적했듯이, 실행 시간에 대한 고려에 포함되어서는 안되는 알고리즘의 결과에 달려있다.BFS 기반 경로 찾기 알고리즘의 실행 시간
나의 추론은 다음과 같습니다. BFS의 각 패스는 e의 배수로 간주되는 정점의 수를 늘립니다. 또한, 정점이 고려 될 때마다, 그것은 e 오퍼레이션이다. 따라서 각 패스는 v (패스의 정점 수) × e입니다. 그리고 만약 v가 1이고 e가 e^2라면, v * e는 e + e^2 + e^4 등이다. 다른 접근법은 고려되는 엣지의 개수에 따라 실행 시간을 고려하는 것이다. . 길이 N의 가장자리는 N 개의 작업을 취합니다. 따라서 E 에지와 평균 에지 길이가 N 인 그래프의 경우 O (N * E)입니다. 그러나 이것은 알고리즘 작동 중에 고려되는 그래프의 부분에만 적용되며 해당 부분 집합의 크기는 시작과 끝점 사이의 거리에 따라 선형 적으로 확장되지 않으므로 O()를 어렵게 만듭니다 .
아이디어 ...?
dijstra보다 어떻게 더 빠릅니까? 이것은 정말로 긴 에지를 가진 그래프에 대해 끔찍한 성능을 가질 수 있습니다 ... – moowiz2020
작은 에지 길이로 더 빠를 수 있습니다. 가장자리 길이가 길면 끔찍하게 느려질 수도 있습니다. – joshlf