동빈나 자바스크립트 강의 #Ch10 다익스트라 알고리즘

최단 경로 문제

한 지점에서 다른 모든 지점까지의 최단 경로 -> 다익스트라 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로 -> 플로이드 워셜 알고리즘

다익스트라 동작 과정

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 (3-4번 반복)
   -> 최단 거리 테이블을 갱신 하지 않고, 우선 순위 큐에 삽입하는 방식도 사용 가능

기본적으로 그리디 알고리즘 유형에 속함

동작과정

Heap 사용

연결 돼있는 곳에서 가장 작은 값을 가진 곳을 찾은 다음 그것과 자신의 직통과 값을 비교해봄

처리한 노드는 다시 방문하지 않음

간선의 갯수만큼 우선순위 큐에 들어감

---

플로이드 워셜 알고리즘

2차원 테이블에 최단 거리 정보를 저장
다이나믹 프로그래밍 유형에 속함

동작 과정

각 단계마다 A에서 특정한 노드 K를 거쳐 B로 갈 때 더 짧아지는 경우
바로 B로 가는 것이 아니라 AK, KB로 갱신하며 확인

한번에 가는 값이 없으면 무한대로 값이 적혀 있음

1번을 거치는 값, 파란 부분은 안 바뀜

빨간색으로 돼있는 부분이 갱신 될 수 있는 부분
1. 3번에서 2번으로 가는 방법

3번에서 1번, 1번에서 2번으로 가는 방법이 2 + 1 이므로 최단거리 3

2번을 거치는 값

2번에 대한 대각선은 안 바뀜

...생략

---

소스코드 예시