[ Algorithm ] 최단경로 알고리즘

최단경로 알고리즘, 다익스트라(Dijkstra)

음의 가중치가 없는 그래프에서 한 정점에서 모든 정점까지의 최단거리를 각각 구하는

알고리즘을 에츠허르 "다익스트라(Edsger Wybe Dijkstra)"라는 컴퓨터 과학자가 만들었다.

그렇기 때문에 음의 간선이 존재하지 않는 최단경로 알고리즘을

"다익스트라" 알고리즘이라고 부른다.

 

최단경로 알고리즘 동작과정

최단거리 테이블은 각 노드에서 현재노드까지의 최단 거리 정보를 가지며

처리 과정에서 더 짧은 경로를 찾아다니며 더 짧은 경로로 값을 갱신한다.

1. 출발 노드를 설정
2. 최단거리 테이블을 초기화
3. 방문하지 않은 노드 중 최단거리 비용이 가장 적은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 최단거리 테이블에 갱신한다.
   < 우선순위 큐에 삽입하는 방식으로 사용가능 >
5. 3번, 4번 과정을 끝날때까지 반복한다.

 

플로이드 알고리즘

전산학자 로버트 플로이드(Robert W Floyd)가 만든 알고리즘이다.

모든 노드에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘으로

다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다.

플로이드 워셜은 2차원 테이블을 통해서 최단거리 정보를 저장하며

다이나믹프로그래밍에 속하기도 한다.

< 단계별로 점화되기 때문에 점화식이기도 하다. >

• 플로이드 워셜의 점화식
  [ A에서 B로가는 거리보다 K를 거쳐가는 A - K - B 의 거리가 더짧은지 체크 ]
  D[A][B] = Math.min(D[A][B], D[A][K] + D[K][B])

 

벨만포드 알고리즘

미국의 두 수학자 "리처드 벨만(Richard Bellman)"과 "카탈리스트인 포드(Alfonso Shimbel)"에 의해

독립적으로 개발된 알고리즘이다. 리처드 벨만의 "벨만"과 카탈리스트인 포드의 "포드"를 따서

"Bellman-Ford Algorithm"으로 불리게 되었다. 벨만포드 알고리즘은 음수의 간선이 포함되어도

최단거리를 계산할 수 있는 최단경로 알고리즘이다. 하지만 경로를 탐색하다 음수순환이 존재하면

무한루프에 빠져 값을 반환할 수 없게된다

 

음수순환이란?

알고리즘을 통해 경로를 탐색하면서 계속해서 가장 짧은 거리를 찾아야하는 갱신해주어야 하지만

특정 경로에서 사이클이 생겼을때 모두 거쳐 갔을때 음수가 되는 경우 사이클을 계속해서 돌면서

값이 작아지기 때문에 음수의 순환이되고 음의 무한인 노드가 되어버린다. 그렇기 때문에

음수순환이 발생하는지에 대해 검사를 해주어야 한다.

 

벨만포드 알고리즘 동작 과정

1. 출발 노드 설정
2. 최단거리 테이블 초기화
3. 아래 과정을 N - 1만큼 반복해준다.
   3-1. 모든 간선 E개를 하나씩 체크한다.
   3-2. 각 간선을 거쳐서 다른 노드로 가는 최단거리의 비용을 테이블에 갱신한다.
   
   
4. < 음수 순환을 체크하기 위해서는 3번 과정을 한 번 더 수행한다. >
   최단거리 테이블이 갱신되다면 음수순환이 존재

 

마치며...

최단경로 알고리즘을 학습할때 벨만포드 알고리즘이 가장 어려웠다. 특히 음의 순환의 경우 이해하는데 꽤 애를 먹었는데 잘 생각해보면... 최소값(최단경로)을 찾는 문제에서 사용했기 때문에 탐색을 할때 계속해서 작은 수가 발견되면 자연스럽게 무한으로 감소한다는 것은 당연한 것이었는데 말이다. 항상 차근차근 발단부터 연관성을 가지고 이해해야 한다는 것을 다시금 느끼게되는 학습이었다.