[코테준비] 다익스트라 알고리즘, 벨만-포드 알고리즘

다익스트라 알고리즘

하나의 정점에서 다른 “모든” 정점으로 가는 최단 경로를 측정하는 알고리즘

 

다시 다익스트라 구현 순서도

1. 출발 노드 설정
2. 출발 노드를 기준으로 각 노드의 최소비용 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적게드는 노드 선택 (이동한다는 개념을 가져야한다)
4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소비용 갱신
5. 3번 4번 과정 반복

어떻게 구현하나요?

DP + heap을 활용한다

DP로 최단거리를 기억하고

heap을 통해 토탈 최단 거리를 구해 최단경로를 추적한다

 

힙을 쓰면 O(n log n), 안 쓰면 O(N**2)

→ 힙은 속도에 이점만 있을 뿐 다익스트라와는 관계가 없다

 

+

힙정렬은 불안정정렬이다

따라서 다익스트라에서도 같은 거리여도 어떤 값이 먼저 나올지는 정해지지 않는다

 

장점

그래프가 큰 경우에도 사용할 수 있다

 

단점

가중치가 음수면 사용할 수 없다

 

왜?

다익스트라는 정점을 지날 수록 가중치가 증가한다는 전제로 쓰여진 알고리즘이다. 그래서 다익스트라 알고리즘은 방문한 노드를 다시는 재방문하지 않는다.

 

착각하지 말자!!

다익스트라는 그리디 알고리즘을 기반으로 했다. 모든 거리를 확인하는게 아니다!

최소거리로 이동하고 다시 최소거리를 찾는 알고리즘이다.

그러니 모든 간선을 확인하지 않기 때문에 음수의 간선을 지나지 않으면 음수를 적용하지 못한 최단거리가 나올 수도 있다.

모든 거리 확인하는게 아니기 때문에 min, max 안 쓴다. 그냥 원래 값보다 작으면 힙에 넣는 것.

 

그럼 음의 가중치는 어떻게 하나요?

벨만-포드 알고리즘을 써라

 

벨만-포드 알고리즘

edge를 한 개 쓸 때 갈 수 있는 거리, 두 개 쓸 때 거리 … N-1번째 거리를 비교해서 시작-도착 최단거리를 구하는 방법

edge를 늘려가면서 각 노드에 도착할 수 있는 최단거리를 비교한다.

 

어떻게 구현하나요?

시작점을 기준으로 생각하는게 아니다

시작 정점은 0으로 초기화만 해주고 모든 간선에 대해 갱신을 진행하는 것

 

[Algorithm] Bellman-Ford Algorithm (벨만-포드 알고리즘)

자세한건 벨만-포드 블로그 글을 확인하자

 

벨만-포드도 음의 사이클이 있으면 구할 수 없다는 한계가 있다.

그래서 구현의 마지막에는 음의 사이클을 구해줘야한다

 

다익스트라 예제 문제

[Python] [백준] 1238번: 파티

[Python] [백준] 1238번: 파티

예제 풀이 프로세스

heapq를 사용

1. 입력값 받기
   1. 무한대 선언 INF = int(1e9)
   2. 노드 그래프 그리기
      1. graph[a] = (index,cost) a번째 노드에 연결된 노드들을 리스트에 넣어둔다 그러니까 0을 제외하고 [1]부터 입력한다
2. 탐색
   1. 기본 거리리스트를 만든다 이때 모든 값은 INF
      1. 이 거리리스트도 위에 노드 그래프와 같은 특징을 가진다 distance[a] = 0 시작노드는 거리가 0이기 때문에
   2. heapq생성 후 (0,start) 초기출발점 heappush
   3. 무한루프 while
      1. heappop으로 정보를 가져옴
      2. for문 graph에서 연결된 노드의 정보를 가져와서 거리를 측정
      3. 거리가 기존 거리리스트와 비교했을때 작으면 저장
      4. heap에도 저장
3. 모든 노드에 대해서 다익스트라 실행, 결과 도출

 

+ 23.10.21

백준 1916번 최소비용 구하기

 

다익스트라에서 힙을 쓰는 이유는 현재 좌표를 기억하기 위한 큐의 역할과 백트래킹 때문이다.

-> 그렇기 때문에 다익스트라에서 가장 먼저 도착점에 도달하는 값이 최소값

 

큐를 쓰는 점과 최소거리를 구하는 방식을 보면 BFS와 동일함

-> 다익스트라는 BFS의 알고리즘 중 하나라고 보면 된다.

 

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

시간이 빡빡하게 되어있어서 백트래킹 제대로 안하면 시간초과가 났다

 

+ 23.10.23

다익스트라는 BFS가 아니다.

힙을 써서 시간 최적화를 한 것은 맞지만 모든 경로를 확인하지 않기 때문에 BFS라 볼 수는 없다.

다익스트라는 그리디 알고리즘의 일종