[AL] 8. 최단 경로 알고리즘

8. 최단 경로 알고리즘

1. 최단 경로(Short Path) 알고리즘
2. 다익스트라(Dijkstra) 알고리즘
3. 플로이드-와샬(Floyd-Warshall) 알고리즘

 

1. 최단 경로(Short Path) 알고리즘

1.1. 알고리즘의 종류

1. Single-Source (One-to-All)

   • 하나의 출발 노드로부터 다른 모든 노드까지의 최단 경로
   • Dijkstra Algorithm 을 사용하여 해결

2. Single-Destination

   • 모든 노드로부터 하나의 노드까지의 최단 경로
   • 모든 Edge를 뒤집으면 One-to-All 과 동일함

3. Single-Pair (One-to-One)

   • 하나의 출발 노드로부터 하나의 목적 노드로까지의 최단 경로
   • 시간복잡도에서 One-to-All 보다 비효율적

4. All-Pair (All-to-All)

   • 모든 노드 쌍의 최단 경로
   • Floyd-Warshall Algorithm 을 사용하여 해결

 

 

2. 다익스트라(Dijkstra) 알고리즘

2.1. Logic

• 초기 dist 배열을 모두 INF 값으로 초기화

• 첫 정점을 기준으로 연결되어 있는 정점을 추가해가며 최단 거리를 갱신함

• A → B 인 경우, dist[b] 는 아래의 2개 중 최소값을 저장함

  • 시작점 부터 a 까지의 최소비용 + a → b 의 가중치
  • 기존에 가지고 있던 b 의 최소비용

 

2.2. Relax 연산

// u : 정점1
// v : 정점2
// w : 정점1과 정점2의 가중치
if(dist[v] > dist[u] + w){
  dist[v] = dist[u] + w;
}

 

2.3. 진행 과정

먼저 시작점은 E 이다

E 에서 갈 수 있는 경로는 B 와 D 이다

먼저 D 노드를 보면, 현재 비용은 ∞ 이고, E를 거쳐 갈 수 있는 비용은 2 이다. 이 중 최소값은 2이다

B 노드의 경우, 현재 비용은 ∞ 이고, E를 거쳐 갈 수 있는 비용은 4 이다. 이 중 최소값은 4이다

이제 나머지 정점 중에서 가장 짧은 정점을 가지고 있는 D 를 고른다

D 노드에서 갈 수 있는 경로는 B 와 C 이다

B 의 현재 비용은 4 이고, D 를 거치는 비용은 3 이다. 이 중 최소값은 3이다

C 노드의 경우 현재 비용은 ∞ 이고, D 를 거치는 비용은 3 이다. 이 중 최소값은 3이다

이런 식으로 진행 하다보면 최소 경로를 모두 구할 수 있다

 

 

3. 플로이드-와샬(Floyd-Warshall) 알고리즘

3.1. Logic

• 두 정점 사이에 간선이 존재하지 않는다면 dist 배열에 INF 를 설정

• 만약 간선이 존재한다면 가중치를 설정

• i → j 의 최단 경로는 k를 지나는 경우와 지나지 않는 경우 중 하나이다

  • 정점 i 와 j 의 경우를 탐색할 때, k는 모든 정점을 반복문으로 탐색
  • i → j 의 비용 과 i → k + k → j 의 비용 중 최소값을 저장

 

3.2. 소스 코드 (C++)

int dist[15][15];
int n;

int floyd(){
  
  for(int k=1; k<=n; k++){
    for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
        if(dist[i][j] > dist[i][k] + dist[k][j]){
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
    
}

 

3.3. 정리

Case : 정점 V 개 , 간선 E 개

다익스트라 알고리즘

• 시작점으로부터 나머지 정점까지의 최단거리를 구할 때
• 공간 복잡도 : V^2 (인접행렬) , V+E (인접리스트)
• 시간 복잡도 : V^2 (인접행렬) , E logV (인접리스트+우선순위 큐)

플로이드 와샬 알고리즘

• 각 정점간 최단 경로를 구할 때
• 공간 복잡도 : V^2
• 시간 복잡도 : V^3

장단점

• 만약 간선 수가 많은 경우 플로이드 알고리즘 이 유리할 수 있음
• 한 점으로부터 각 정점까지의 최단거리만 필요하다면 다익스트라 가 압도적으로 빠름
• 그래프의 음의 가중치 간선이 존재한다면 다익스트라 X , 플로이드 O