그래프, 경로, 최단경로
- 그래프 : 정점과 간선으로 이루어진 자료구조
- 경로 : 간선들을 순서대로 나열한 것
- 최단경로 : 시작 정점부터 목표 정점까지의 가중치의 합이 최소가 되는 경로
다익스트라 알고리즘
- 양의 가중치를 가진 최단 경로 탐색에서 사용하는 알고리즘
- 각 지점에서 최단 경로를 찾아가는 그리디한 방법이자 최단 경로의 부분경로 역시 최단 경로인 DP 기반의 알고리즘
- 음의 가중치가 있는 경우 그리디한 접근으로 무한루프에 빠질 가능성이 있어 이때는 플로이드 와샬 사용
- 한 정점에서 모든 정점으로의 최단 경로를 구할 때
- 예시, 프로그래머스 배달 문제
import heapq
from collections import defaultdict
def di(dic, start, N, K) :
cnt = 0
distances = {}
for n in range(1, N+1) :
distances[n] = float('inf')
distances[start] = 0
q = []
heapq.heappush(q, [0, 1])
while q:
cur_dis, cur_node = heapq.heappop(q)
if distances[cur_node] < cur_dis:
continue
for nxt, dis in dic[cur_node]:
distance = cur_dis + dis
if distance < distances[nxt]:
distances[nxt] = distance
heapq.heappush(q, [distance, nxt])
for key in distances:
if distances[key] <= K :
cnt += 1
return cnt
def solution(N, road, K):
dic = defaultdict(list)
for node in road :
dic[node[0]].append(node[1:])
dic[node[1]].append([node[0], node[2]])
answer = di(dic, 1, N, K)
return answer
플로이드 와샬 알고리즘
벨먼-포드 알고리즘
- 가중 그래프, 시작점에서 종점까지ㅡ이 경로 중 간선의 가중치의 합이 가장 작은 것을 구하는 문제
- 음의 가중치도 가능
- 플로이드와샬은 O(n3), 벨먼-포드는 O(nm), 정점의 수 n, 간선의 수 m, 가중치 변경 작업을 N회 시행
- 시작점은 0, 나머지는 무한대로 설정
- 시작 정점의 가중치 + 간선의 가중치 = 도착 정점의 가중치
- 계산한 가중치가 현재보다 작으면 업데이트를 해줌
다익스트라 알고리즘과 벨먼-포드 알고리즘 비교
- 모두 시작점에서 모든 정점으로의 최단경로를 구할 때 사용 가능
- 다익스트라는 음의 가중치 있는 경우 사용 못함, 벨먼-포드는 가능
플로이드 와샬 알고리즘과 다익스트라 알고리즘 비교
- 플로이드 와샬은 각 정점간 최단 경로를 구할 때, 다익스트라는 한 정점에서 모든 정점으로의 최단경로를 구할 때 사용
- 다익스트라 알고리즘은 음의 가중치가 있는 경우 사용 못 함
- 간선의 수가 많을 때는 플로이드와샬이 유리하나 시작점에서 모든 정점으로의 최단경로만 구할 때는 다익스트라가 빠름
에이스타 알고리즘(A*)
최소 신장 트리(MST)
- 신장트리 : 그래프 내의 모든 정점(n)을 간선(n-1)으로 연결한 트리
- 최소 신장 트리 : 최소한의 비용으로 신장트리 형성
- 참고 포스팅
프림 알고리즘
- 임의의 정점과 인접한 정점 중에서 최소 비용 간선을 선택하며 MST를 이어 나가는 방법
- 밀집 그래프일때 크루스칼보다 효과적(정점이 적고 간선이 많을 때, 밀집그래프- 간선의 수가 최대간선수에 가까운 그래프)
- visited 등을 통해 이미 방문한 정점 체크
크루스칼 알고리즘
- 가중치가 적은 간선부터 선택(오름차순으로 정렬), 선택한 간선 수를 기록해줌
- 이미 정점이 집합에 포함되어 있으면 패스, 선택한 간선 수가 n-1이면 브레이크
- 간선이 별로 없는 그래프일때 효과적