그래프 알고리즘 정리 - 파이썬

그래프 알고리즘 분류

그래프는 최소신장트리와 최단거리 문제로 나눌 수 있다.

각기 사용되는 알고리즘이 다르다.

 

 

---

MST (최소신장트리)

1. 크루스칼 - 간선기준 가장 작은것부터 연결, 음의 간선 가능
2. 프림 - 정점기준 정점에 연결된 가장 작은 간선으로 연결, 음의 간선 가능

간선 개수가 적으면 크루스칼, 정점 개수가 적으면 프림 적용

 

최단경로

1. 다익스트라 (우선순위큐 heapq 사용, 단일 정점 최단경로)
2.  벨만-포드 (음의 가중치, 경로 추적 가능)
3. 플로이드 와샬 (음의 가중치, 3중포문, 모든 정점 사이 최단거리)
4. shortest path faster algorithm

 

---

크루스칼

• 간선을 정렬하여 가중치가 작은 간선부터 연결
• 사이클이 발생하면 연결하지 않음
• O(E * log(E))

 

---

프림

• 한 정점의 간선 중 가중치가 가장 작은 간선과 연결된 정점 방문
• O(E * log(V)) - 우선순위 큐 사용시

https://deep-learning-study.tistory.com/595

[알고리즘] 프림 알고리즘(Prim Algorithm)

 

 

---

플로이드 와샬

• 모든 최단 경로를 구함
• 출발 정점이 따로 없다
• 음의 가중치 간선 가능
• 2차원 배열의 자료구조
• 거쳐가는 정점을 기준으로 최단 거리를 구한다.
• 3중 for문으로 모든 최단 경로 탐색
• 시간복잡도: O(V^3)
• 공간복잡도: O(V^2)

https://it-garden.tistory.com/247

자세한 구현 방법

https://dev-room.tistory.com/64?category=789120 

 

 

---

벨만-포드

• 다익스트라의 조건에 음의 간선이 있다는 조건이 포함될 때 사용
• 음수 가중치가 있는 그래프의 한 정점부터 다른 노드까지 최단 거리
• 음수 사이클 존재 여부 확인 가능
• 시간복잡도: O(VE)
• 공간복잡도: 
• 다익스트라보다 느림
• V번 반복하며 매 반복마다 모든 간선을 확인해 갱신

https://deep-learning-study.tistory.com/587

 

---

다익스트라

• 한 정점으로부터 다른 정점까지의 최단 거리
• O(E * log(V))
• 양수 간선만 가능
• 매 상황에서 가장 비용이 적은 노드 선택

https://www.youtube.com/watch?v=F-tkqjUiik0

전에 풀었던 문제: https://cme10575.tistory.com/101

[백준] 1504 특정한 최단경로 파이썬