[자료구조/알고리즘] 최단 경로 알고리즘, 다익스트라, 플로이드-와샬

최단 경로 알고리즘은 그래프 탐색 관련 문제로 그래프 상에서 특정 지점으로부터 다른 지점까지 가장 짧은 경로를 찾는 알고리즘이다. 대표적으로 다익스트라와 플로이드-와샬 알고리즘이 있다.

 

1) 다익스트라(dijkstra)

다익스트라가 제안한 몇 개의 알고리즘 중 가장 잘 알려진 것이 최단 경로 알고리즘이어서 그냥 다익스트라 알고리즘이라 부르기도 한단다. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하며, 음의 간선이 없어야만 정상적으로 동작할 수 있다. 기본적으로 매 상황 가장 비용이 적은 노드를 선택하는 과정을 반복하기 때문에, 일종의 그리디 알고리즘이며 계속해서 최단 거리 테이블을 갱신하기에 동적 프로그래밍의 아이디어를 사용하기도 한다. 추가적인 작업을 더해준다면, i에서 j로 이동할 때의 최단 경로가 어떤 노드들의 순서로 구성되었는지 파악할 수 있다.

 

[동작 과정]

① 출발 노드 설정 및 최단 거리 테이블 초기화

② 방문하지 않은 노드 중 가장 짧은 노드 선택

③ 해당 노드를 거쳐 다른 노드로 가는 비용을 계산, 최단 거리 테이블을 갱신.

④ 모든 노드를 반복할 때까지 ②, ③의 반복

 

구현 과정에서 우선순위 큐를 활용하면 시간 복잡도 면에서 효율을 추구할 수 있다.

(O(n**2) -> O(E*logV) _ E: 간선의 수, V: 꼭짓점의 수)

 

[구현 과정]

① 최단 거리 테이블 초기화(모든 값을 충분히 큰 값(INF = 10**9)으로 설정)

② 시작 노드 우선 순위 queue에 삽입. 이때 (시작 위치로부터의 거리, 노드 위치)의 튜플을 삽입한다.

③ queue에서 하나씩 꺼내면서 해당 노드 위치까지의 거리가 현재 거리 테이블에 저장된 값보다 작은 경우, 해당 노드가 가진 모든 간선을 탐색하며 인접한 노드들까지의 거리 테이블을 갱신

④ ③의 과정에서 갱신되는 노드의 정보는 다시 queue에 삽입. 

 

연습 문항(구현 예시) _ 경로 x: https://mingchin.tistory.com/302

[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1504번 _ 특정한 최단 경로

연습 문항(구현 예시) _ 경로까지 구하기: https://mingchin.tistory.com/304

[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 11779번 _ 최소비용 구하기 2

2) 플로이드-와샬(Floyd - Warshall)

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘. 2차원 테이블에 i에서 j까지의 최단 거리 정보를 테이블에 저장하며, 이를 계속해서 업데이트 해나가는 동적 프로그래밍 개념이 사용된다. n개에 노드에 대해 실행한다면, n번에 걸쳐 n**2의 거리 테이블을 모두 탐색하면서 현재 저장된 거리와 특정 노드 k를 거쳐갈 때의 거리를 비교해 더 작은 값으로 업데이트 하므로, O(n**3)의 시간 복잡도를 가진다. 또한 구현 과정에서 몇 개의 노드를 거치는 지는 확인할 수도 있지만, 어떤 노드들을 어떠한 순서로 지나며 최단 경로를 만들었는지는 알기 어렵다.

 

[구현 과정]

① 최단 거리 테이블 초기화(모든 값을 충분히 큰 값(INF = 10**9)으로 설정), 이때 이 테이블은 n*n이어야 한다.

② 3중 for문으로, 각각 k의 노드를 거칠 때에 대해 최단거리 테이블 업데이트.

 

연습 문항(구현 예시): https://mingchin.tistory.com/301

[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 11404번 _ 플로이드