[트리] 최단경로 찾기 : 플로이드-워셜, 다익스트라, 벨만포드

최단경로 문제

• 가중치가 있는 그래프에서, 가중치의 합이 최소가 되는 경로를 찾는 것.
• 종류
  • 단일 출발 / 출발지1, 도착지n : 하나의 노드에서 출발해, 여러 도착지를 방문할 때 어느 노드까지 가는 경로가 최단인지 찾는 문제
  • 단일 도착 / 출발지n, 도착지1 : 여러개의 노드에서 출발해, 하나의 도착지를 방문할 때 어느 노드부터 출발해야 경로가 최단인지 찾는 문제. 출발지1, 도착지n의 위 경우의 간선 방향을 뒤집어서 똑같이 해결한다.
  • 출발지n, 도착지n' : 여러개의 노드에서 출발해, 여러 도착지를 방문할 때 최단 경로를 찾는 문제. 가상의 출발 노드 하나를 만들어 (진짜 출발노드와 가상 출발노드를 잇는 간선이 필요한데 이때 간선의 가중치는 0임) 해결한다.
  • 전체 쌍 / 출발지n, 도착지n : 모든 노드들의 사이의 최단 경로를 찾는 문제. (위 경우와는 다르다. 도착지와 출발지를 교집합한 것과 합집합 한 것이 똑같음.)
  • 단일 쌍 / 출발지1, 도착지1 : 하나의 노드에서 출발해, 하나의 도착지를 방문할 때 최단 경로를 찾는 문제.

⓪ BFS (완전탐색 방법)

• 간선의 가중치가 모두 동일한 경우에 가장 빠르게 해결할 수 있다.

① 플로이드-워셜 Floyd-Warshall (+동적계획법 접근)

• 간선에 음의 가중치 사이클이 존재하지 않을 때 최단경로를 구할 수 있음. (즉, 음의 가중치가 있어도 되긴 함)
• 전체 쌍 문제에 적용
• 동적계획법으로 접근 ($dp[x][y] = dp[x][k] + dp[k][y]$)
  • x, y 두 노드 사이의 최단 경로는 '바로 잇는 간선'(x-y), '경유지를 거쳐 가는 간선'(x-k-y)이 있다.
  • ✨ 최단경로인 x-k-y 가 있다면, x-k, k-y (subset) 역시 각각 최단 경로임
    • 즉, 경유지 a를 이용해 최단 경로를 한 번 업데이트하고,
    • 다음으로 경유지 b를 이용해 최단 경로를 구하는데, 이때 경유지 a를 이용해 구했던 최단 경로(subset)을 사용하게 됨 !! ✨
• 🧾 모든 경유지에 대해 모든 정점에서 모든 정점으로 가는 최단경로를 확인하기 때문에, $V^3$번 연산이 일어나게 된다.
  • (대충 $V < 500$으로 나옴.)
• 🧾 인접행렬로 구현. $V^2$ 공간복잡도

백준 11404 플로이드 소스코드

② 다익스트라 Dijkstra

• 간선에 음의 가중치가 존재하지 않을 때 사용가능.
• 단일 출발/단일 도착, 단일 쌍 문제에 적용.

• 하나의 노드(i)에서 갈 수 있는 간선들(edges[i])을 뽑아서 → [다른 노드(j)의 현재 최단경로(dist[j])와] vs. [다른 노드(j)를 현재 노드(i)를 거쳐갔을 때]를 비교한다. 이때 dist[j]가 뜻하는건, 시작노드 S에서 j로 갈 수 있는 최단경로를 말한다. 비교한 후 가장 작은 dist값을 가지는 노드를 선택해서 작업을 반복한다.
  • 이를 갈 수 있는 모든 노드에 대해 반복하는데, 노드들은 최대 한 번씩만 방문할 수 있다. 음의 가중치가 없는 것을 가정하므로, 다른 노드를 거치면 거칠수록 경로 비용이 증가하기 때문에 한 번 뽑힌 최단경로, 노드는 고려하지 않아도 된다.
  • 🧾 (1) 즉, 모든 노드를 방문하는 최대 $V$번의 연산이 일어난다.
  • 🧾 (2) 그리고 한 노드를 통해 dist를 업데이트 한 후 다음 최단경로, 노드를 뽑을 때 우선순위 큐를 사용하면 push $E$번, pop 비용인 $\log{E}$번 연산이 일어난다. (우선순위 큐에는 간선 정보와 도착 노드 정보가 들어가고, 최대 간선 수가 들어갈 수 있다.)
  • 🧾 ➡ $E\log{E}$의 시간복잡도를 가지게 된다. 이때 중복 간선을 포함하지 않을 때 $E < V^2$ 이다. 즉, $E\log{V^2} = 2E\log{V} = O(E\log{V})$의 시간복잡도를 갖는다.
• 🧾 인접리스트로 구현.

③ 벨만-포드 Bellman-Ford-Moore

• 간선에 음의 가중치가 존재할 때도 사용가능.
  • 음의 사이클 존재 여부도 판단 가능. (E번 이상의 경로 갱신이 일어날 때)
• 단일 출발/단일 도착, 단일 쌍 문제에 적용

• 초기상태는