Bellman Ford 알고리즘에 대한 오래된 시험, 불필요한 것이 필요합니까?

Question

우리는 100 개의 꼭지점을 가진 지시 된 그래프를 가지고 있습니다. v1 -> v2 -> ... v100이고 모든 에지 가중치는 1입니다. 우리는 v1에서 다른 꼭지점까지 모든 최단 경로를 찾기 위해 bellman-ford를 사용하려고합니다. 각 단계에서이 알고리즘은 임의의 순서로 모든 에지를 검사합니다. 각 단계에서 다른 모든 정점과의 최단 거리 v1이 변경되지 않으면이 알고리즘이 중지됩니다. 단계 수는 모서리의 순서를 확인하는 것과 관련이 있습니다. 이 문제의 최소 및 최대 단계는 무엇입니까?

해결책 : 2

(100) 나는 생각한다

우리는이 그래프가있는 경우 : V1-> V2-> V3 -> ...-> V100을 우리가 V1이있는 경우 우리가 2. 필요 -> v2, V1-> V3, V1-> V4, ... 우리는 100을 필요로하고 v99v100, v98v99, ..., v3v2, v2v1을 갖는다면 마지막으로 100을 필요로합니다.

누구든지 나를 도울 수 있습니까?

Answer 1

이 V1-> V2-> V3 -> ...-> V100 우리는 당신이 V1-> V2, V2-> V3 (순서대로 가장자리를 얻을 가정, 2

진정한 필요 , v3-> v4 ...).

V1-> V2, V1-> V3, V1-> V4 모든 거리가 1 (시작 노드에서 직접 가장자리 거기 때문에 ... 우리는 100

거짓 필요 모든 다른 사람에게), 그 다음 가장자리를 한 번 통과하면 올바른 결과 (가장자리의 순서와 상관없이)를 얻고 두 번째 통과는 중단됩니다.

v99v100는 v98v99는, ..., v3v2는 v2v1 우리는 당신이 첫 번째 예에서와 동일한 그래프를 가지고 가정, 100

사실 필요하지만, 가장자리는 반대 순서입니다.