최단 경로 개념

코딩 테스트에는 주로 '다익스트라'와 '플로이드 워셜'이 출제 된다.

둘다 방향이 있는 그래프이다.

주로 최단 경로 전체를 출력하는 문제보다는 단순히 최단 거리만을 출력하는 문제가 많다.

아래 설명에서 시간복잡도의 N는 노드의 개수, E는 간선의 개수를 나타낸다.

 

다익스트라

- 특정 노드에서 모든 노드까지의 최단 거리들을 구함

- 최단 거리 저장 자료 구조 : 특정 노드에 대한 리스트 사용 (1차원 벡터)

- 시간 복잡도 : 리스트를 순회하는 알고리즘 = O(N^2) / 힙을 이용한 알고리즘 = O(ElogN)

- 음의 간선이 없을 때 사용 가능

 

플로이드 워셜

- 모든 노드에서 모든 노드까지의 최단 거리들을 구함

- 최단 거리 저장 자료 구조 : 모든 노드에 대한 리스트 사용 (2차원 벡터)

- 시간 복잡도 : O(N^3)

 

- V x V 크기의 인접 행렬을 가지고 플로이드 워셜을 수행하면 V x V 크기의 최단거리 행렬이 나온다.

- 기본적으로 인접 행렬의 대부분의 값은 INT_MAX로 초기화하지만, (i, i) 위치에 있는 대각선 값들은 경우에 따라 0으로 초기화할 수도 있고 INT_MAX로 초기화할 수도 있다.

 

1) 자기 자신에게 돌아올 수 없는 경우

- 인접 행렬의 대각선 값들을 0으로 초기화한다.

- 플로이드 워셜 수행 후, 최단거리 행렬의 대각선 값들이 무조건 0으로 나온다.

 

2) 자기 자신에게 돌아올 수 있는 경우

- 인접 행렬의 대각선 값들을 INT_MAX로 초기화한다.

- 플로이드 워셜 수행 후, 최단거리 행렬의 대각선 값들이 INT_MAX로 유지되거나 INT_MAX가 아닌 다른 값으로 갱신된다. (INT_MAX로 유지되면 자기 자신으로 돌아오는 경로가 없다는 뜻)