최단 경로 알고리즘

최단 경로 알고리즘: 가장 짧은 경로를 찾는 알고리즘 a.k.a 길 찾기 문제

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

  : 특정한 노드에서 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘 (하나의 노드 → 다른 모든 노드)

 

  ⁎ 매번 가장 비용이 적은 선택 → 그리디 알고리즘

  ⁎ '음의 간선'이 없을 때 효율적으로 작동

  ⁎ 과정

   ① 출발 노드 선택 ←보통 문제에서 주어짐

   ② 최단 거리 테이블(1차원 배열) 초기화 ← 처음에는 자기 자신을 제외하고 무한으로 설정

   ③ 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택

   ④ 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 ← 그리디한 부분

   ⑤ ③과 ④ 반복

 

  ⁎ 구현방법

   1. 간단한 다익스트라 알고리즘 - O(V²)

    : 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계의 1차원 리스트(배열)의 모든 원소를 확인 → 순차탐색

    - 노드의 개수가 10000개 이상이면 힘들다. (오래 걸림)

 

   2. 개선된 다익스트라 알고리즘 - O(ElogV)

    : 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 탐색할 때 우선순위 큐 사용

     + 우선순위 큐: 우선 순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 (힙 자료구조 사용)

    

※ 플로이드-워셜(Floyd-Warshall) 알고리즘 - O(N³)

  : 모든 노드에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘 (모든 노드 → 모든 노드)

  ⁎ (최단 경로를 저장할 때) 2차원 배열 사용 (paht[i][j]=i번째 노드에서 j번째 노드까지 가는 최단 경로)

  ⁎ '현재 노드를 거쳐가는' 모든 경로 확인 

  ⁎ 현재 확인하고 있는 노드를 제외하고 서로 다른 노드 쌍(A,B)을 선택

  ⁎ A → 현재 확인하고 있는 노드(k) → B의 비용을 확인하고 갱신

     ⇨ D[A][B] = min(D[a][b], D[a][k]+D[k][b]) → DP (3중 반복문 사용)