박성우.md

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘

다익스트라 알고리즘

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘!!!

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3, 4번을 반복한다.

힙 정렬을 사용하여 구현한다면 시간복잡도는 O(NlogN)이다.

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우 사용하는 알고리즘!!!

N개의 노드일 때, N번의 단계를 O(N$^2$) 연산을 하므로 총 시간 복잡도는 O(N$^3$)이다.

1. 그래프의 인접 행렬을 초기화한다. 경로가 없는 경우 무한대 값을 가진다.
2. 3중 반복문을 사용하여 모든 정점 쌍에 대한 최단 경로를 찾는다.
3. 중간 정점을 선택한 후, 그래프의 모든 정점 쌍에 대해 최단 경로를 갱신한다.
4. 반복문을 통해 모든 중간 정점을 고려하여 최단 경로를 찾는다.