0
저는 그래프 이론을 배우고 있으며 도움이 필요합니다. bfs를 사용하여 그래프의 모든 정점 사이의 최단 경로에 대한 알고리즘이 필요합니다. 나는 bfs가 어떻게 동작하는지 알지만 그래프의 모든 버텍스들 사이의 최단 경로를 찾는 알고리즘을 "다시 만든다"는 것은 모른다.bfs를 사용하는 모든 버텍스 간의 최단 경로
A
답변
0
Yerken이 말한 것처럼 가장 간단한 방법은 각 노드에 대해 반복되는 BFS입니다. 그것의 시간 복잡도는 O ((v + e) * v)이며, 여기서 v와 e는 각각 정점과 모서리의 수이다. O (1) < e < O (v^2)이므로 그래프가 매우 조밀하면 O (v^3) 알고리즘입니다. 그러나 그래프가 희박하고 복잡성이 O (v^2)이면 복잡성이 O (v * e * log (v)) = O (v * log (v))이기 때문에 반복 된 Dijkstra의 경우 더 빠르게 수행 될 수 있습니다.).
또는 Floyd-Warshall 알고리즘을 O (v^3)로 시도 할 수도 있지만 경로가 아닌 거리 만 제공합니다.
모든 정점 사이의 최단 경로를 찾으려면 무엇을 의미합니까? 입력과 출력을 제공 할 수 있습니까? –
정점 A, B, C, D가있는 그래프를 작성하면 모두 도달 할 수 있으므로 각 정점에 대해 A-B, A-C, A-D, B-C, B-D, C-D –
을 실행해야합니다. – Yerken