똑똑한 코드 작성을 위한 실전 알고리즘

270

똑똑한 코드 작성을 위한 실전 알고리즘

이 알고리즘이 왜 동작할까? 노드가

N

개인 그래프를 관찰해보면 그래프에 존재할 수 있는 가

장 긴 경로는 간선이

N

–

1

개보다 많을 수 없다.

i

에 대한

for

루프가 그래프에서 모든 간선을

완화하기 위해

N

–

1

회 반복을 시도하고 나면 그래프에서 가장 긴 경로가 처리되어 그 시점에

최단 총 거리를 완화하는 간선이 더는 남아 있지 않아야 한다. 이런 이유로

for

루프는

N

회 반

복한다. 루프의 마지막에서 알고리즘이 간선을 완화할 수 있다면 해당 그래프는 음의 순환을

포함한다.

7.7

모든 쌍의 최단 경로 문제

이 장에서 설명한 탐색 알고리즘은 지정된 시작 노드에서 탐색을 시작한다. 그 이름에서 알 수

있듯

모든 쌍의 최단 경로

all

-

pairs

shortest

paths

는 그래프에서 두 노드

u

와

v

간의 누적된 간선 가중

치의 가능한 최단 경로를 계산하는 문제다. 무향 그래프에서

u

에서

v

까지 최단 경로는

v

에서

u

까지의 최단 경로와 동일하다. 무향 그래프와 유향 그래프 모두 노드

v

에서

u

까지 도달하지 못

하는 경우에는 최단 경로 거리가 무한대가 된다. 유향 그래프에서는

u

에서

v

까지 도달하지 못

하더라도

v

에서

u

까지는 도달 가능할 수 있다.

탐색은 어떤

u

와

v

간의 실제 최단 경로를 복구할 수 있도록 정보를 ...