1
O (E)에서 임의의 가중치를 갖는 그래프에서 단일 소스에서 정점까지의 최단 경로를 찾는 방법이 있지만 최단 경로에 7이 있으면 걱정할 필요가 있습니다. 가장자리 이하.O (E) 최단 경로
Bellman-Ford 알고리즘은 O (E)의 실행 시간이 가장 좋습니다. 여기에 적용됩니까? 모든 정점에 < = N 단계와 최단 경로를 알고있는 경우
A
답변
1
, 그것은 당신이 할 수 긴 경로를 가장자리 반복하고 평가하여 < = N + 1 단계를 최단 경로를 계산하기 쉽게 하나 하나 만들어라. N = 0에서
, 소스 정점을 최단 경로의 길이를 0을 가지고 있으며, 다른 모든 정점까지의 최단 경로의 길이는 무한 (즉, 당신이 얻을 수 없다)이있다. 당신은 당신이 조금 있다면 당신은 O (E)의 총 실행 시간, < = N = 7 단계에서 얻을 수있는 모든 곳에서 가장 짧은 경로를 찾기 위해 가장자리를 통해을 7 번 반복해야 데이터 구조에주의하십시오.
복잡도는 동일하므로 알고리즘을 그에 맞게 수정해야합니다. 많은 경우가 제거되어 실행 시간이 더욱 빨라질 것입니다. – mangusta