그래프

08-5 벨만-포드

벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 음수 가중치 에지가 있어도 수행할 수 있다는 점과 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다는 점이다. 시간 복잡도는 O(VE)를 가지고 있다.

모든 에지를 N-1(N은 노드의 개수)만큼 돌려주고 음수 사이클을 판단하기 위해 한 바퀴 더 돌려주는 것이 포인트이다. 만약 마지막으로 한 번 더 돌렸을 때 값이 업데이트가 된다면 음수 사이클이 존재한다는 뜻이다.

08-6 플로이드-워셜

플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 음수 가중치 edge가 있어도 수행할 수 있다는 점과 동적 계획법의 원리를 이용해 알고리즘에 접근한다는 점이다. 시간 복잡도는 O(V3)로 구하는 속도는 느린 편이다. 만약 노드의 수가 100-200개로 작고 최단거리를 구하는 문제라면 플로이드-워셜 알고리즘을 고려하자.

플로이드-워셜의 핵심 이론

for 경유지 K에 관해 (1 ~ N) #N은 노드 개수 
	for 출발 노드 S에 관해 (1 ~ N)
    	for 도착 노드 E에 관해 (1 ~ N)
        	D[S][E] = min(D[S][E], D[S][K] + D[K][E]

플로이드-워셜은 3중 for문의 형태로 간결하게 나타낼 수 있다. 실제로 쓰인 파이썬 코드는 다음과 같다.

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if distance[i][k] + distance[k][j] < distance[i][j]:
                distance[i][j] = distance[i][k] + distance[k][j]

주의해야 할 점은 k가 가장 바깥에서 감싸준다는 것이다. 헷갈릴 수 있으모로 외워놓으면 편리할 것이다.