『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

다익스트라 (Dijkstra)

• 다익스트라(dijkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
  • 출발 노드와 모든 노드 간의 최단 거리를 탐색한다.
  • 에지는 항상 모두 양수이다.
• 노드 수를 $V$, 에지 수를 $E$라고 했을 때 시간 복잡도는 $O(ElogV)$이다.

핵심 이론

1. 인접 리스트로 그래프 구현하기

   • 인접 행렬도 구현해도 좋지만, 시간 복잡도 측면에서 N의 크기가 클 것을 대비해 인접 리스트를 선택하여 구현하는 것이 좋다.
   • 그래프의 연결을 표현하기 위해 인접 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언하여 연결한다.
   • 인접 행렬로 구현하면 없는 자리도 모두 검색해야 한다.

2. 최단 거리 배열 초기화하기

   • 출발 노드는 0, 이외의 노드는 무한으로 초기화한다.
   • 이때, 무한은 적당히 큰 값을 사용하면 된다. (예를 들어 99,999,999)

3. 최단 거리 배열에서 현재 값이 가장 작은 노드 고르기

4. 최단 거리 배열 업데이트하기

   • 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트 한다.
   • 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트 한다.
   • 연결 노드의 최단 거리는 다음과 같이 두 값 중 더 작은 값으로 업데이트 한다.
   $Min(선택\ 노드의\ 최단\ 거리\ 배열의\ 값+에지\ 가중치, 연결\ 노드의\ 최단\ 거리\ 배열의\ 값)$

5. 과정 3~4를 반복해 최단 거리 배열 완성하기

   • 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열을 만들어 처리한다.
   • 모든 노드가 선택될 때까지 반복한다.

벨만-포드 (Bellman-Ford)

• 벨만-포드(bellman-ford-moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
  • 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다.
  • 음수 가중치 에지가 있어도 수행할 수 있다.
  • 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.
• 노드 수를 $V$, 에지 수를 $E$라고 했을 때 시간 복잡도는 $O(VE)$이다.
• 실제 알고리즘 코딩 테스트에서는 벨만-포드 알고리즘을 사용해 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제된다.

핵심 이론

1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기
   • 벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다. (edge 클래스는 일반적으로 노드 변수 2개와 가중치 변수로 구성되어 있다)
   • 최단 경로 리스트는 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.
2. 모든 에지를 확인해 정답 리스트 업데이트하기
   • 최단 거리 리스트에서 업데이트 반복 횟수는 $노드 개수-1$이다.
     노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 $N-1$이기 때문이다.
   • 모든 에지 $E=(s,e,w)$에서 다음 조건을 만족하면 업데이트를 실행한다.

     • 음수 사이클이 없을 때 최대 에지 개수가 나오려면 사항 트리 형태에서 양 도착 노드를 선택해야 한다.

       # 정답 리스트: D
       # 에지의 출발 노드: s, 종료 노드: e, 에지의 가중치: w
       IF (D[s] != 무한대이며 D[e] > D[s] + w일 때)
       	D[e] = D[s] + w로 리스트의 값을 업데이트

   • 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트의 값은 시작점에서 K개의 에지를 사용했을 때 각 노드에 대한 최단 거리이다.
     
   • 음수 사이클이 없을 때 $N-1$번 에지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려주는 정답 리스트가 완성된다.
3. 음수 사이클 유무 확인하기
   • 음수 사이클 유무를 확인하기 위해 모든 에지를 한 번식 다시 사용해 업데이트되는 노드가 발생하는지 확인한다.
   • 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이고, 음수 사이클이 존재하면 이 사이클을 무한하게 돌 수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다.
   • 즉, 2단계에서 도출한 정답 리스트가 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻이 된다.

플로이드-워셜 (Floyd-Warshall)

• 플로이드-워셜 (Floyd-Warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
  • 모든 노드 간에 최단 경로를 탐색한다.
  • 음수 가중치 에러가 있어도 수행할 수 있다.
  • 동적 계획법의 원리를 이용해 알고리즘에 접근한다.
• 노드 수를 $V$라고 했을 때 시간 복잡도는 $O(V^3)$이다.
  • 따라서 플로이드-워셜을 사용하는 문제라면 노드 개수(N)의 범위가 다른 그래프에 비해 작게 나온다. (200~300 등)

핵심 이론

• 플로이드-워셜 알고리즘의 핵심 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다.
  • 즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다.
• 이 원리로 다음과 같은 점화식을 도출할 수 있다.
  $D[S][E]=Math.min(D[S][E], D[S][K]+D[K][E])$

구현 방법

1. 리스트를 선언하고 초기화하기

   • D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의한다.
   • S와 E의 값이 같은 칸은 0, 다른 칸은 무한대로 초기화한다.
   • 여기서 S==E는 자기 자신에게 가는데 걸리는 최단 경로값을 의미한다.

2. 최단 거리 리스트에 그래프 데이터 저장하기

   • 출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때 D[S][E]=W로 에지의 정보를 리스트에 입력한다.
   • 이로써 플로이드-위셜 알고리즘은 그래프를 인접 행렬로 표현한다는 것을 알 수 있다.

3. 점화식으로 리스트 업데이트하기

   • 기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 리스트의 값을 업데이트한다.

   # 노드 개수는 N
   for 경유지 K에 관해 (1~N)
   	for 출발 노드 S에 관해 (1~N)
   		for 도착 노드 E에 관해 (1~N)
   			D[S][E] = Math.min(D[S][E], D[S][K]+D[K][E])

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런