코테 연습) 최단경로

 

 

1. 최단 경로 알고리즘

- 그래프상에서 가장 짧은 경로를 찾는 알고리즘

- 다익스트라 알고리즘과 플로이드 워셜 알고리즘을 성능, 구현 난이도, 역할에 대하여 비교하면 다음과 같다

알고리즘 종류	시간 복잡도	구현 난이도	역할
다익스트라	O(ElogV)	어려운 편	한 지점에서 다른 모든 지점까지의 최단 경로를 계산한다
플로이드 워셜	O(V³)	쉬운 편	모든 지점에서 다른 모든 지점까지의 최단 경로를 계산한다

 

 

2. 다익스트라 알고리즘

- 단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택한 뒤에, 그 노드를 거쳐 가는 경우 확인하여 최단 거리를 갱신하는 방법 

- 우선순위 큐를 이용하여 소스코드를 작성할 수 있다

 

 

3. 플로이드 워셜 알고리즘

- 다이나믹 프로그래밍을 이용하여 단계마다 거쳐 가는 노드를 기준으로, 최단거리 테이블을 갱신하는 방식으로 동작한다

- 다음의 점화식만 기억한다면 큰 어려움 없이 구현 가능

D[a][b] = min(D[a][b], D[a][k] + D[k][b])

- 다음과 같은 3중 반복문을 이용해 구현할 수 있다

for k in range(1, n + 1):
	for a in range(1, n + 1):
    	for b in range(1, n + 1):
        	adj[a][b] = min adj[a][b], adj[a][k] + adj[k][b])

 

 

출처 / 유튜브 [동빈나 - (이코테2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬]