📕 다익스트라
- 시간 복잡도는 O(ElogE)
- 하나의 정점에서 모든 정점으로 가는 최단거리를 구함.
- 우선순위 큐 사용
1. 시작 노드 결정 0으로 초기화 후 우선순위 큐에 담음
2. 나머지 노드 무한대로 초기화
3. 우선순위 큐에서 pop한 후 그 노드에서 갈 수 있는 노드를 확인
4. 더 빠르다면 갱신하고 우선순위 큐에 넣는다.
5. 방문했거나, 더 느리다면 continue
6. 우선순위 큐가 빌 때까지 3-5번을 반복한다.📕 벨만포드
- 시간 복잡도는 O(V*E) ~= O(V^3)
- 하나의 정점에서 모든 정점으로 가는 최단거리를 구함.
- 가중치가 음수인 경우도 적용 가능
- 가중치가 사이클을 이루는 경우 사용 불가능
1. 시작 노드 결정 0으로 초기화
2. 나머지 노드 무한대로 초기화
3. 나머지 노드 방문하며 주변 노드에 방문하는 최단거리 갱신 (v-1 번 반복)
4. 한 번 더 방문하면 업데이트 되는지 확인 (사이클 확인, 사이클이 있다면 false)📕 플로이드 워셜
- 시간 복잡도는 O(V^3)
- 모든 정점에서 모든 정점으로 가는 최단거리를 구함.
- 그러므로 그래프는 2차원 배열
- 가중치가 음수인 경우도 적용 가능
1. 인접행렬을 저장할 2차원 배열을 만들고 무한대로 초기화
2. 간선정보저장, 제자리 0으로 초기화
3. 경유지를 기준으로, 해당 경우지를 거쳐가는게 빠르다면 갱신
(i 가 경유지라면, A[j][k] = min(A[j][k],A[j][i]+A[i][k]) )
4. 모든 정점을 경유지로 선정해 3번 반복
Jazzing👨💻