[알고리즘] 최단 경로 알고리즘 - JavaScript

최단 경로 알고리즘? 

그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘이다. 

 

대표적인 최단 경로 알고리즘은 다음과 같다.

• DFS
• 다익스트라
• 벨만-포드
• 플로이드 와샬

목적에 따라 알고리즘을 선택할 수 있다. 

 

BFS, DFS 

그래프의 간선 가중치가 모두 같을 때 적합하다. 

2차원 배열로 구성된 지도에서 최단 거리를 찾아야 한다면 BFS, DFS로 푸는 경우가 많다. 

다익스트라 알고리즘

그래프의 간선 가중치가 각각 다른 경우 적합하다. 

우선 큐를 이용해서 만들 수 있으며, 시간 복잡도는 V가 정점의 수, E가 간선의 수라면 

O(E log V) 이다.

 

작동 방법

1. 시작점을 제외한 모든 정점의 거리를 무한으로 설정한다. 시작은 0

2. 시작점을 선택한다. 

3. 선택한 정점에서 갈 수 있는 정점의 거리를 
    현재 정점까지의 값 + 목적지 정점까지의 간선의 값으로 갱신한다. 

4. 선택한 정점을 방문 처리한다. 

5. 이미 방문한 정점과 무한인 정점을 제외하고 가장 최단 거리인 정점을 선택한다. 

6. 더 이상 방문할 수 있는 정점이 없을 때까지 반복한다. 

7. 도착점의 값을 확인한다.