[CS] 최단 경로

최단 경로의 종류

• 단일 출발 최단 경로

    어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는 문제

    음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘

• 단일 도착 최단 경로

    모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제

    음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘

• 단일 쌍 최단 경로

    어떤 정점 v에서 w로 가는 최단 경로를 찾는 문제 

    음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘

• 전체 쌍 최단 경로

    모든 정점 쌍들 사이의 최단 경로를 찾는 문제 (플로이드-워셜 알고리즘)

 

다익스트라 알고리즘

음의 가중치를 갖지 않는 그래프에서 어떤 한 정점에서부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘

각 정점을 최대 한 번씩만 방문하여 최단 거리를 확정한다.

아직 방문하지 않은 정점들 중 최단 거리인 점을 찾아 방문하여 최단 거리를 확정하고 이를 반복한다.

총 \(V \times V\) 번 연산이 필요하다. 따라서, \(O(V^2)\) 의 시간복잡도를 가진다.

 

우선순위 큐 또는 힙 자료구조를 이용하면 더욱 개선된 알고리즘이 가능하다.

우선순위 큐의 맨 앞 또는 최소 힙의 맨 위에 있는 정점을 꺼내어 D[j] = D[i] + W 로 갱신한다. 

간선의 개수가 E개일 때, 최소 힙에는 최대 E개의 정점이 들어가 있다.

하나의 정점을 꺼낼 때마다 \(logE\) 의 연산이 필요하므로 총 \(ElogE = ElogV^2 = 2ElogV\) 이 되어 시간복잡도는 \(O(ElogV)\) 이다.

출처 : 위키백과

 

벨만-포드 알고리즘

가중 그래프에서 어떤 한 정점에서부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘 (음의 가중치 가능)

최단 거리를 구하기 위해서 (V - 1)번 E개의 모든 간선을 확인한다.

음의 사이클의 존재 여부를 확인하기 위해서 한 번 더 E개의 모든 간선을 확인한다.

이때, 갱신되는 최단 거리가 있다면 음의 사이클이 있다는 의미로 해석할 수 있다.

총 \(V \times E\) 번 연산이 필요하다. 따라서, \(O(VE)\) 의 시간복잡도를 가진다.

출처 : 위키백과

 

플로이드-워셜 알고리즘

가중 그래프에서 모든 정점 사이의 최단 경로를 구하는 알고리즘

순환만 없다면 음의 가중치도 가능하다.

기본적으로 동적계획법으로 접근한다.

dis[A][B] > dis[A][K] + dis[K][B] 라면 갱신한다.

가능한 모든 경유지에 대해서 모든 정점에서 모든 정점으로 가는 최단 거리를 확인하므로 연산횟수는 \(V^3\) 이고 시간복잡도는 \(O(V^3)\) 이다.