[개념]다익스트라/플로이드와샬

다익스트라

다이나믹 프로그래밍을 기반으로 한 최단거리 찾는 문제

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 때 사용하는 알고리즘

노드 선택 기준은 비용이 가장 적은 정점

작동 방식

1. 시작 노드를 설정한다.
2. 시작 노드에서 각 노드까지 걸리는 시간을 초기화한다.
3. 비용이 가장 적고 아직 방문 하지 않은 노드를 선택해서 이 노드부터 다른 노드들까지의 거리를 계산한다.
4. 만약 기존 값보다 적으면 값을 초기화 해준다.
5. 3번과 4번 과정을 반복해서 모든 노드가 방문하면 종료한다.

시간 복잡도

단순 선형 탐색 시 O(N^2)

힙 구조를 활용하면 O(N * log N)

 

 

플로이드와샬

다이나믹 프로그래밍을 기반으로 한 최단거리 찾는 문제

모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘

거쳐가는 정점이 노드 선택 기준  

 

작동 방식

1. 각 노드에서 노드로 가는 거리 초기화
2. 각 노드를 하나씩 선택해서 거쳐 가는 경우와 바로 가는 경우를 비교해서 값 갱신

예) 만약 노드 1을 거쳐가는 경우

우선 노드 1과 관련이 없는 경우만 for문을 돌려 탐색한다.

2-3 을 확인한다면 : (2-3) vs (2-1) + (1-3) 바로 가는 경우와 1을 거쳐가는 경우를 계산해서 더 작은 값으로 갱신 

 

시간 복잡도

O(N^3) : 노드가 n개일 때, n 번의 단계를 수행하며 단계마다 O(N^2)의 연산을 함

 

 

출처
https://blog.naver.com/ndb796/221234427842