DataStructure & Algorithm

Chapter 10. Shortest Path Problem

MoYoungmin 2020. 7. 1. 15:03

1. 최단 경로 문제란?

최단 경로 문제란 두 노드를 잇는 가중치의 합이 가장 짧은 경로를 찾는 문제이다. 가중치가 모두 동일하면 BFS로 찾을 수 있다.

  • srouce가 1개이고 destination이 1 개인 경우
  • srouce가 1개이고 destination이 n 개인 경우
  • srouce가 n개이고 destination이 n 개인 경우

 

Lemma의 정리

최단경로의 부분 경로는 모두 최단 경로이다.

[그림 1] Lemma 시각화

2. Dijkstra's Algorithm

간선의 가중치가 음수가 아닐 때 사용하며 Prim's Algorith과 매우 유사한 방식으로 진행된다. 여기서도 정점들은 UnSeen Verticies, Tree Verticies, Fringe Verticies에 속하며 모든 정점들을 Tree Verticies로 넣는 과정으로 진행된다.

 

과정

  1. 모든 Vertex를 UnSeen Verticies로 초기화한다.
  2. source를 고르고 Tree Verticies에 넣은 다음 incidentEdges에 있는 정점을 Fringe에 넣는다.
  3. d(src, src) = 0 으로 모두 초기화 한다. 여기서 d(src,dst)는 src->dst까지 Min Weight Sum Cost를 의미한다.
  4. Fringe Verticies가 빌 때까지 5-6 작업을 반복한다.
  5. d(s, t) + w (t, v)가 최소가 되는 v를 선택한다. 이때 t는 Tree Verticies에 있는 정점 중 하나이며 v는 Fringe Verticies에 있는 정점 중 하나이다. 쉽게 말하면, Srouce로 부터 Fringe에 있는 정점들 중 Path Weight 합이 가장 작은 것을 선택하는것이다. 여기서 d 함수는 src->tree 까지 최단 경로 합을 말하며, w 함수는 tree - vertex의 가중치를 나타낸다.
  6. 선택된 vertex를 tree에 넣고 vertex의 incidentEdges를 통해 나온 반대편 정점의 상태에 따라 7-8-9 작업을 수행한다.
  7. UnSeen Vertex : Fringe Vertex에 추가
  8. Tree Vertex : 무시하고 진행
  9. Fringe Vertex : 기존에 있는 값과 d(s, t) + w(t, v)값을 비교하여 더 작은 값으로 업데이트를 수행한다.
  10. 이후 d(s,v)를 d(s, v) = s(s, t) + w(t, v)로 Update를 수행한다.

 

[그림 2] Dijkstra's Algorithm Example

복잡도

위 알고리즘의 복잡도는 Prim's Algorithm과 매우 유사하다. Priority Queue의 구현 방식에 따라 복잡도가 나눠진다.

Unsorted Array로 구현 : O(n^2)

Heap으로 구현 : O(m x log n)

 

Correctness

[그림 3] Dijkstra's Algorithm Correctness

선택한 노드가 최선이고 추후에 변경 하지 않는다는 점에서 Greedy Algorithm과 유사하다.

 

다익스트라 알고리즘을 수행하면 src로부터 여러 목적지에 대하여 최단경로를 알 수 있다. 즉, src가 1개이고 destination이 n개인 문제를 해결 할 수 있다.

물론 다익스트라 알고리즘을 모든 정점에 대하여 수행한다면 n:n 문제 즉, All - Pairs Shortest Paths 문제의 일부를 해결 할 수 있다.

3. All Pairs Shortest Paths

모든 정점 사이의 최단 경로를 구하는 문제로 n:n 문제를 해결하는데 사용된다.

앞서 말한 1:n문제 즉, src가 1개이고 destination이 n개인 문제를 모든 정점에 대해 수행해도 되지만

이번에 "Floyd-warshall Algoritm"을 이용하여 해결할려고 한다.

다익스트라 알고리즘은 가중치가 음수일 때 처리가 어렵지만 Floyd-warshall 알고리즘은 Cycle이 없다면 가중치가 음수여도 구현이 쉽다.

 

Floyd-warshall Algoritm

핵심 아이디어는 거쳐가는 정점을 기준으로 최단거리를 구한다.

k 정점을 기준으로 inComming 정점들과 Outgoing 정점들을 이어주고 이 값과 기존의 값들을 비교하며 진행한다.

 

아래의 알고리즘으로 보면 초기에 가중치에 대하여 2차원 배열을 이용하여 초기화를 진행한다.

이후, 3개의 반복문을 통해 알고리즘을 진행한다. PseudoCode를 보면 k는 거쳐가는 정점을, i는 k를 기준으로 inComing 정점을, j는 Outgoing 정점을 나타낸다.

 

D[i, j] = min(D[i, j] , D[i, k] + D[k , j])

여기서 D[i, j]는 i로부터 j까지 최단 경로를 말하며, 기존에 있던 값과, 현 단계에서 새로 계산된 값과 비교하여 처리를 진행한다.

 

이 방식은 Dynamic Programming과 유사한 방식이다.

[그림 4] Floyd-warshall Algoritm Example

복잡도 : O(n^3)

 

※ Transitive Closure

이 알고리즘 역시 "Floyd-warshall"을 이용하기에 잠깐 적어본다.

그래프에서 임의의 두 정점 u, v 에 대하여 u -> v의 Path가 존재하는지를 바로 알 수 있기 위하여 사용한다. 

아래의 사진을 보면 Adjacent 연산을 많이 수행하므로 인접 행렬이 좋으며 O(n^3)의 복잡도를 가진다.

[그림 5] Transitive Closure Problem

 

4. Dynamic Programming

Dynamic Programming은 아래의 조건을 만족한다.

  • 큰 문제를 작은 문제로 나누어 해결한 후 이를 조합하는 Devide And Comquer 특징
  • Optimal Solution을 구하기 위해 Subproblem이 겹치고, 이러한 문제를 위해 Speed 대신 Space를 사용한다. 

 

즉. 겹치는 문제를 재 계산하는것이 아닌 Space를 활용해 재활용한다. 이를 Memoization이라고 부른다.

만약, Table에 정보가 있다면 저장된 값을 불러오고 Table에 정보가 없다면 이를 계산하고 Table에 정보를 저장한다. 여기서 Table을 프로그래밍을 할 떄 배열을 이용하여 나타낸다.

 

풀이 방식

  1. 최적해의 구조를 안다. 즉, 최적해가 다른 SubProblem으로 이루어짐을 안다.
  2. 재귀적으로, 점화식을 세운다.
  3. 최적해를 계산한다. Ex) 주안역 -> 인하대의 최소 시간을 안다.
  4. 최적 Solution을 구한다. Ex) 주안 -> 인하대의 최소 시간에 대한 Route를 구한다.

 

구현 방식

  • Top - Down 방식 : 재귀함수를 이용해 구현하며 점화식을 이해하기 쉽다는 장점이 있다.
  • Bottom - Up 방식 : 반복문을 이용해 구현하며, 재귀 호출에 대한 Speed, Space를 절약할 수 있다. 하지만 점화식을 이해하기는 힘들다.