자료구조와 알고리즘 - 최단 경로 알고리즘

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. 최단 경로 알고리즘이란?

• 그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘
• BFS, DFS를 활용하여 구할 수 있음
• 종류
  • BFS
  • 다익스트라(Dijkstra)
  • 벨만-포드(Bellman-Ford's)
  • 플로이드 와샬(Floyd Warshall)
• 목적에 따라 선택하기

BFS, DFS

• 그래프의 간선 가중치가 모두 같을 때 적합
• 지도가 주어지고 출발지 -> 목적지까지의 최단 경로를 구할 때

2. 다익스트라(Dijkstra) 알고리즘

• 간선에 가중치가 있고 각각 다른 경우 적합
• Edsger Wybe Dijkstra가 고안
• 우선순위 큐를 이용하여 만듦
• 시간복잡도는 V가 정점의 수, E가 간선의 수 일 때 O(ElogV)

알고리즘

1. 시작점은 0, 나머지는 무한대로 설정
2. 시작점 선택
3. 선택 정점에서 갈 수 있는 정점의 거리를 정점(해당 정점까지의 최단 거리) 값 + 간선(거리) 값으로 갱신
4. 선택한 정점을 방문 처리
5. 이미 방문한 정점과 무한인 정점을 제외하고 가장 최단 거리인 정점을 선택
6. 더 이상 방문할 수 있는 정점이 없을 때 까지 3~5를 반복
7. 도착점의 값을 확인

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript