다익스트라

정의

• 하나의 시작 노드로부터 다른 모든 노드까지의 최단 거리를 구하는 알고리즘

특징

• 다익스트라: 한 지점에서 모든 지점까지 ↔ 플로이드 워셜: 모든 지점에서 다른 모든 지점까지

• A*: 100% 정확한 최단거리 내지 않아도 되고, 정점의 개수가 많아 현실적으로 다익스트라 쓰기 어려운 경우 사용할 수 있는 근사 알고리즘

• 시간복잡도는 O(ElogE) (E: 에지 수)
• 에지 한 개당 우선순위 큐에 최대 한 개의 원소가 추가될 수 있기 때문
• 우선순위 큐에 N개의 원소를 추가하는 시간 복잡도 → O(NlogN)

• 우선순위 큐로 구현 가능

• 단계마다 방문하지 않은 노드 중 가장 최단 거리 짧은 노드 선택한 뒤에, 그 노드를 거쳐 가는 경우를 확인해 최단 거리를 갱신
• 최단 거리 배열에서 현재 값이 가장 작은 노드 고르는 이유)
• 현재 선택한 노드의 최단 거리가 앞으로 변경될 일 없는 고정된 결과여야 해서. 만일 고정된 결과가 아니라면, 다른 노드들에게 잘못된 최단 거리를 전파하게 됨.
• 현재 최단 거리 배열에서 최단 거리가 가장 짧은 노드는 값이 더이상 변경될 일이 없다고 확신할 수 있는 이유)
• 노드의 최단 거리는 다른 노드의 최단 거리 배열의 값(+ 에지 가중치)과 비교해 둘 중 작은 값으로 업데이트될 텐데, 현재 노드의 최단 거리 배열의 값이 배열에서 가장 작다면 다른 어떤 값과 비교해도 항상 더 작아서 업데이트될 일이 절대 없기 때문
• 예시)

• 에지의 가중치가 모두 양수일 때만 사용 가능, 방향/무방향 여부는 상관 없이 사용 가능
• 가중치가 음수인 에지가 있으면 사용할 수 없는 이유)
• 현재 갈 수 있는 노드 중 가장 가까운 노드까지의 거리를 확정할 수 없기 때문
• 예시)

추상화한 과정

1. 그래프를 인접 리스트로 구현하기

2. 최단 거리 배열 초기화하기
• 출발 노드는 0, 이외의 노드는 무한(99_999_999 같이 적당히 큰 값)으로 초기화

3. 최단 거리 배열에서 현재 값이 가장 작은 노드 고르기

4. 최단 거리 배열 업데이트하기
• 현재 선택된 노드에 연결된 에지의 값을 바탕으로 현재 노드와 연결된 노드의 최단거리 값 업데이트
• 최단거리 값을 Min(선택 노드의 최단 거리 배열의 값 + 에지 가중치, 연결된 노드의 최단 거리 배열의 값) 으로 업데이트

5. 모든 노드가 처리될 때까지 과정 3~4를 반복해 최단 거리 배열 완성하기
• 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 배열 만들어 처리

구체화한 과정

1. 우선순위 큐에 (거리,노드) 꼴로 (0, 시작점)을 추가, 최단 거리 배열에 시작점은 0으로, 나머지는 큰 수로 초기화

2. 우선순위 큐에서 거리가 가장 작은 원소(노드)를 선택 (pop)
• 해당 원소의 거리가 최단 거리 테이블에 있는 값과 다를 경우 3번 과정을 수행하지 않고 넘어감
• 원소의 거리가 최단 거리 테이블에 있는 값과 다르다는 건 해당 원소가 우선순위 큐에 들어온 이후로 더 짧은 경로가 등장해서 현재는 쓸모가 없어진 원소라는 의미임
• 우선순위 큐에 원소가 들어오는 상황은, 항상 거리가 더 줄어들었을 때 최단 거리 테이블을 갱신하며 우선순위 큐에 들어온 상황이기 때문임
• 따라서 원소의 거리가 최단 거리 테이블에 있는 값과 다를 땐 해당 원소의 거리는 최단 거리 테이블에 있는 값보다 무조건 더 큼 → 의미 없는 값

3. 선택한 노드와 이웃한 노드들에 대해
• 현재 본인의 최단 거리 테이블 값(최단 거리)보다
• 선택한 노드를 거쳐가는 것이 더 작은 값을 가질 경우
• 최단 거리 테이블 값을 갱신하고 우선순위 큐에 (거리,노드)를 추가

4. 우선순위 큐가 빌 때까지 2~3번 과정을 반복

코드 1

0. 가중치 있는 그래프를 인접리스트로 표현하기

2. 우선순위 큐에 (거리, 노드)꼴로 (0, 시작점)을 추가, 최단 거리 배열에 시작점은 0으로, 나머지는 큰 수로 초기화

3. 우선순위 큐에서 거리가 가장 작은 원소를 pop하여 선택하고, 원소의 거리가 최단 거리 배열의 값과 같은지 확인

4. 선택한 노드와 이웃한 노드들의 최단 거리 갱신되어야 하면, 최단 거리 테이블 값 변경하고 우선순위 큐에 (거리, 노드)를 추가
• 최단 거리 계산 : min(선택 노드의 최단 거리+에지 가중치, 이웃 노드의 최단 거리)
• 최단 거리 갱신 조건 : "선택 노드의 최단 거리+에지 가중치"가 "이웃 노드의 최단 거리"보다 더 작을 때만 최단 거리 갱신

5. 우선순위 큐 빌 때까지 2,3을 반복

코드 2

0. 가중치 있는 그래프를 인접리스트로 표현하기

2. 우선순위 큐에 (거리, 노드)꼴로 (0, 시작점)을 추가, 최단 거리 배열은 큰수로 초기화

3. 우선순위 큐에서 거리가 가장 작은 원소를 선택(pop)하고, 한 번도 선택된 적이 없는 노드라면 최단 거리 배열에 원소의 가중치 값 넣기

4. 선택한 노드와 이웃한 노드가 한 번도 선택된 적이 없는 노드라면, 우선순위 큐에 (거리, 노드)를 추가

5. 우선순위 큐 빌 때까지 2,3을 반복

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main