다익스트라 알고리즘 이란?

• 최단 경로 알고리즘 중 하나

• 특정 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우 사용

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 경우 사용

• 단, '음의 간선'이 없을 때에만 정상적으로 동작

• 매번 가장 거리가 가장 짧은 노드를 선택해서 임의의 횟수의 과정을 반복

---

동작 방식

1. 출발 노드 설정

2. 최단 거리 테이블을 초기화 (다른 모든 노드로 가는 최단거리를 '무한'으로 초기화)

3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

5. 3~4번 과정을 반복

1. 처음 1번 노드에서 자기 자신의 거리는 0이고, 나머지는 무한의 값으로 초기화

2. 출발인 1번 노드를 선택하고, 해당 노드를 거쳐 갈 수 있는 다른 노드(여기서는 2,3번)의 거리를 계산하여 갱신

노드위의 식별값은 최단거리, 이전 노드로, 방문한 노드는 우상단에 * 표시

3. 방문하지 않은 노드 중 가장 짧은 최단 거리 노드(3번)를 선택하고, 해당 노드를 거쳐갈 수 있는 다른 노드를 갱신

4. 3번 노드를 기준으로 다른 노드도 동일하게 반복

2번 노드를 통하면 4번 노드까지의 거리가 3 + 10 = 13이었는데

3번 노드를 통해가면 4 + 8 = 12로 갱신된다.

5. 위 과정을 반복하여 최단거리 테이블을 전부 갱신

즉, 1번 노드에서 다른 모든 노드로 가는 경러와 최단거리를 알 수 있게 되었다.

1번에서 6번으로 가는 최단거리는 12이며, 경로는 1 → 2 → 6이며

1번에서 7번으로 가는 최단거리는 13이며, 경로는 1 → 3 → 5 → 7이 나온다.

---

Code

---

문제풀이

백준 1504

• 최단 경로를 구하는 문제이므로 다익스트라 알고리즘을 사용

• 시작점 → v1 → v2로 가는 방향과
  시작점 → v2 → v1로 가는 2가지 방향을 모두 구해주어야 함