그래프
정점과 간선으로 이루어진 자료구조이다.
구현 방법
- 인접 행렬
그래프의 노드를 2차원 배열로 만든 것이다. 인접한 정점이라면 1, 아니면 0을 저장한다.- 장점
- 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1) 의 시간 복잡도면 가능하다
- 구현이 비교적 간단하다
- 단점
- 모든 정점에 대해 간선의 정보를 입력해야 하므로 O(n^2)의 시간복잡도가 소요된다
- 무조건 2차원 배열이 필요하므로 필요 이상의 공간이 낭비된다
- 장점
- 인접 리스트
그래프의 노드들을 리스트로 표현한것입니다. 주로 정점의 리스트 배열을 만들어 관계를 설정해줌으로써 구현합니다.- 장점
- 정점들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능하다
- 필요한 공간만큼만 사용하기 때문에 공간 낭비가 적다
- 단점
- 특정 두 점이 연결되어있는지를 확인하려면 인접행렬에 비해 시간이 오래 걸린다
- 구현이 비교적 어렵다
- 장점
최단경로
최단 경로 문제
- 단일 출발(single-source) 최단 경로
: 단일 노드 v에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제 (다익스트라, 벨만-포드) - 단일 도착(single-destination) 최단 경로
: 모든 노드들로부터 출발하여 그래프 내의 한 단일 노드 v로 도착하는 가장 짧은 경로를 찾는 문제. 그래프 내의 노드들을 거꾸로 뒤집으면 단일 출발 최단경로문제와 동일 - 단일 쌍(single-pair) 최단 경로 : 주어진 꼭지점 u와 v에 대해 u에서 v까지의 최단 경로를 찾는 문제
- 전체 쌍(all-pair) 최단 경로 : 그래프 내 모든 노드 쌍들 사이의 최단 경로를 찾는 문제. (플로이드-와샬)
Dijkstra
하나의 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. A, B, C, D, E, F 노드가 있을 때 하나의 정점 A를 기준으로 A-B, A-C, A-E ... 까지의 최단 거리를 구할 수 있다. 이전에 구한 값을 재사용한다는 의미에서 다이나믹 프로그래밍, 항상 가장 짧은 거리를 선택한다는 점에서 그리디 알고리즘으로 분류하기도 한다.
과정
- 출발 노드 설정
- 출발 노드를 기준으로 각 노드의 거리를 저장
- 방문하지 않은 노드 중에서 가장 짧은 거리를 선택
- 해당 노드를 거쳐가는 경우와 해당 노드를 거쳐가지 않는 경우를 비교하여 최단거리 갱신
- 3, 4과정을 반복
구현
선형탐색으로 구현하면 O(n^2) , 힙을 이용하면 O(NlogN)
- 선형탐색
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
# 주어지는 그래프 정보 담는 N개 길이의 리스트
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1) # 방문처리 기록용
distance = [INF] * (n+1) # 거리 테이블용
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
# 방문하지 않은 노드이면서 시작노드와 최단거리인 노드 반환
def get_smallest_node():
min_value = INF
index = 0
for i in range(1, n+1):
if not visited[i] and distance[i] < min_value:
min_value = distance[i]
index = i
return index
# 다익스트라 알고리즘
def dijkstra(start):
# 시작노드 -> 시작노드 거리 계산 및 방문처리
distance[start] = 0
visited[start] = True
# 시작노드의 인접한 노드들에 대해 최단거리 계산
for i in graph[start]:
distance[i[0]] = i[1]
# 시작노드 제외한 n-1개의 다른 노드들 처리
for _ in range(n-1):
now = get_smallest_node() # 방문X 면서 시작노드와 최단거리인 노드 반환
visited[now] = True # 해당 노드 방문처리
# 해당 노드의 인접한 노드들 간의 거리 계산
for next in graph[now]:
# 시작->now 거리 + now->now의 인접노드 거리
cost = distance[now] + next[1]
# cost < 시작->now의 인접노드 다이렉트 거리
if cost < distance[next[0]]:
distance[next[0]] = cost
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print('도달 할 수 없음')
else:
print(distance[i])- 힙
import heapq
import sys
def dijkstra(start):
# 초기 배열 설정
distances = {node: sys.maxsize for node in graph}
# 시작 노드의 거리는 0으로 설정
distances[start] = 0
queue = []
# 시작 노드부터 탐색 시작 하기 위함. (거리, 노드) - 거리, 노드 순으로 넣은 이유는
#heapq 모듈에 첫 번째 데이터를 기준으로 정렬을 진행하기 때문 (노드, 거리) 순으로
#넣으면 최소 힙이 예상한대로 정렬되지 않음
heapq.heappush(queue, (distances[start], start))
# 우선 순위 큐에 데이터가 하나도 없을 때까지 반복
while queue:
# 가장 낮은 거리를 가진 노드와 거리를 추출
current_distance, node = heapq.heappop(queue)
# 파이썬 heapq에 (거리, 노드) 순으로 넣다 보니까 동일한 노드라도 큐에
#저장이 된다 예시: queue[(7, 'B'), (10, 'B')]
# 이러한 문제를 아래 조건문으로 이미 계산되어 저장한 거리와
#추출된 거리와 비교하여 저장된 거리가 더 작다면 비교하지 않고 큐의 다음 데이터로
#넘어간다.
if distances[node] < current_distance:
continue
# 대상인 노드에서 인접한 노드와 거리를 순회
for adjacency_node, distance in graph[node].items():
# 현재 노드에서 인접한 노드를 지나갈 때까지의 거리를 더함
weighted_distance = current_distance + distance
# 배열의 저장된 거리보다 위의 가중치가 더 작으면 해당 노드의 거리 변경
if weighted_distance < distances[adjacency_node]:
# 배열에 저장된 거리보다 가중치가 더 작으므로 변경
distances[adjacency_node] = weighted_distance
# 다음 인접 거리를 계산 하기 위해 우선 순위 큐에 삽입
#(노드가 동일해도 일단 다 저장함)
heapq.heappush(queue, (weighted_distance, adjacency_node))
return distances
graph = {
'A': {'B': 10, 'C': 3},
'B': {'C': 1, 'D': 2},
'C': {'B': 4, 'D': 8, 'E': 2},
'D': {'E': 7},
'E': {'D': 9},
}
result = dijkstra('A')
print(result)Floyd Warshall
모든 정점에서 모든 정점으로 가는 최단거리를 구하는 알고리즘이다. 이 알고리즘의 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단거리를 구하는 것이다.
과정
라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복합니다.
구현
from sys import stdin
from math import inf
n = int(stdin.readline())
m = int(stdin.readline())
# 이동 최소비용을 저장할 2차원 배열
cost = [[inf] * n for _ in range(n)]
for _ in range(m):
a, b, c = map(int, stdin.readline().split())
cost[a-1][b-1] = min(cost[a-1][b-1], c)
# 플로이드 와샬 알고리즘 적용
k in range(n):
cost[k][k] = 0
for i in range(n):
for j in range(n):
cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])
# 결과 출력
for row in cost:
for i in range(n):
# 갈 수 없는 경로인 경우, 0 출력
if row[i] == inf:
row[i] = 0
print(row[i], end=" ")
print()Bellman-Ford
그래프에서 시작 정점으로부터 다른 정점까지의 최단 경로를 찾기 위한 알고리즘이다. 다익스트라 알고리즘과는 달리 음의 가중치도 계산할 수 있다. 이 알고리즘의 시간복잡도는 O(VE)이다.
과정
- 시작 정점을 결정한다
- 시작 정점에서 각각 다른 정점까지의 거리 값을 무한대로 초기화한다.
- 현재 정점에서 인접 정점들을 탐색하여, 기존의 저장되어있던 인접 정점까지의 거리보다 현재 정점을 거쳐 인접 정접까지 도달하는 거리가 더 짧을 경우 값을 갱신한다.
- 3번의 과정을 (V-1)번 반복한다.
- 위 과정을 모두 마치고 난 후 거리가 갱신되는 경우가 생긴다면 음수 사이클이 존재한다는 것이다.
구현
import sys
import collections
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split()) # 노드 수, 간선 수 입력 받기
edges = [] # 모든 간선에 대한 정보를 담는 리스트 생성
dist = [INF] * (n+1) # 최단 거리 테이블을 모두 무한으로 초기화
# 그래프 생성
for _ in range(m):
u, v, w = map(int, input().split()) # 노드, 인접 노드, 가중치
edges.append((u, v, w))
# 벨만 포드 알고리즘
def bf(start):
dist[start] = 0 # 시작 노드에 대해서 거리를 0으로 초기화
for i in range(n): # 정점 수만큼 반복
for j in range(m): # 매 반복 마다 모든 간선 확인
node = edges[j][0] # 현재 노드 받아오기
next_node = edges[j][1] # 다음 노드 받아오기
cost = edges[j][2] # 가중치 받아오기
# 현재 간선을 거려서 다른 노드로 이동하는 거리가 더 짧은 경우
if dist[node] != INF and dist[next_node] > dist[node] + cost:
dist[next_node] = dist[node] + cost
# n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
if i == n-1: # n-1번 이후 반복에도 값이 갱신되면 음수 순환 존재
return True
return False
# 벨만 포드 알고리즘 수행
negative_cycle = bf(1)
if negative_cycle:
print('-1')
else:
# 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리 출력
for i in range(2, n+1):
if dist[i] == INF: # 도달할 수 없는 경우 -1 출력
print('-1')
else: # 도달할 수 있는 겨우 거리를 출력
print(dist[i])