[알고리즘 이론] 다익스트라(feat. 프림), 벨만-포드, 플로이드-워샬 개념 차이

다익스트라(feat. 프림), 벨만-포드, 플로이드-워샬

알고리즘 개념 차이

---

이때까지 헷갈렸던 알고리즘의 개념을 정리해봤습니다 !

 

1. 다익스트라 알고리즘(feat. 프림 알고리즘)

2. 벨만-포드 알고리즘

3. 플로이드-워샬 알고리즘

---

1. 다익스트라 알고리즘(feat. 프림 알고리즘)

다익스트라 알고리즘은 하나의 정점에서 모든 정점으로 가는 최단 거리를 구한다.

프림 알고리즘도 그리디 방식으로 간선을 선택한다.

 

프림 알고리즘은 모든 정점을 사이클없이 이을 때의 최소 비용을 구한다.

각 정점에 자신과 연결된 간선의 가중치를 저장하여 최소 비용을 업데이트한다.

 

다익스트라 알고리즘은 각 정점에 시작점으로부터의 경로를 저장하여 시작 정점이 바뀔 때마다 다른 결과값이 저장된다.

말로만 하면 이해가 안될 수 있기에 그림으로 표현해보겠다.

 

 

a,b,c,d,e 정점이 주어졌을 때 모든 정점을 연결하되,  사이클을 피해 최소 비용을 구하는 알고리즘이 프림 알고리즘이다.

a,b,c,d,e 정점이 주어졌을 때 a->d와 같이 특정 정점까지의 최단 거리를 구하는 알고리즘이 다익스트라 알고리즘이다. 

 

2. 벨만-포드 알고리즘

벨만-포드 알고리즘은 다익스트라 알고리즘에서 가중치가 음수인 경우에도 적용 가능한 버전이다.

 

3. 플로이드-워샬 알고리즘

플로이드-워샬 알고리즘(동적 계획)은 모든 정점에서 모든 정점으로 가는 최단 거리를 구한다.

---

다음 포스팅에서 만나요잉 !