JUNGLE 240330 (W02)
KRAFTON JUNGLE Week 02
1. Keywords
다익스트라 알고리즘 (Dijkstra)
음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘
의사 코드
function Dijkstra(Graph, Source):
dist[source] ← 0 // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0--
prev[source] ← undefined // 출발지 이전의 최적 경로 추적은 없으므로 Undefined
create vertex set Q // 노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작
for each vertex v in Graph: // Graph안에 있는 모든 노드들의 초기화
if v ≠ source: // V 노드가 출발지가 아닐 경우 (출발지를 제외한 모든 노드!)
dist[v] ← INFINITY // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 (모든 노드들을 초기화하는 값)
prev[v] ← UNDEFINED // V노드의 최적경로 추적 초기화
add v to Q // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가
// 요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함.
while Q is not empty: // Q 집합이 공집합 아닐 경우, 루프 안으로!
u ← vertex in Q with min dist[u] // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작
remove u from Q // U 노드를 방문한 것이므로 Q집합에서 제거
for each neighbor v of u: // U의 이웃노드들과의 거리 측정
alt ← dist[u] + length(u, v) // 출발지 노드부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리
// = source to U + V to U = source to U
if alt < dist[v]: // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우
dist[v] ← alt // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈
prev[v] ← u // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈
return dist[], prev[] // 계산된 거리값과 목적지를 리턴
구현 코드 (Python)
영상 참고: Click!!
infinity = float("inf")
def make_graph():
# tuple = (cost, to_node)
return {
'A': [(10, 'B'), (30, 'C'), (15, 'D')],
'B': [(20, 'E')],
'C': [(5, 'F')],
'D': [(5, 'C'), (20, 'F')],
'E': [(20, 'F')],
'F': [(20, 'D')]
}
def dijkstras(G, start='A'):
shortest_paths = {}
unvisited = dict.fromkeys(G.keys())
for node in unvisited:
shortest_paths[node] = (infinity, None) # (최단 거리, 이전 노드)
shortest_paths[start] = (0, None)
while unvisited:
min_node = None
for node in unvisited:
if min_node is None:
min_node = node
elif shortest_paths[node][0] < shortest_paths[min_node][0]:
min_node = node
for edge in G[min_node]:
cost, to_node = edge
new_distance = cost + shortest_paths[min_node][0]
if new_distance < shortest_paths[to_node][0]:
shortest_paths[to_node] = (new_distance, min_node)
del unvisited[min_node]
return shortest_paths
def print_shortest_path(shortest_paths, start, end):
path = []
node = end
while node is not None:
path.append(node)
node = shortest_paths[node][1]
if path[-1] == start:
print(f'Shortest path from {start} to {end}: {path[::-1]}')
print(f'Distance: {shortest_paths[end][0]}')
else:
print(f'No path from {start} to {end}')
def main():
G = make_graph()
start = 'A'
end = 'F'
shortest_paths = dijkstras(G, start)
print_shortest_path(shortest_paths, start, end)
main()
- 이전 노드의 정보를 튜플로 같이 저장
- 최단 경로는 이전 노드의 정보를 활용해서 역추적으로 출력
플로이드-와샬 (Floyd-Warshall)
- 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘
- 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다.
구현 코드 (Python)
def floyd_warshall(graph):
# 그래프의 정점의 개수
V = len(graph)
# 최단 경로를 저장할 행렬 초기화
# 최단 경로가 없는 경우는 무한대(infinity)로 설정
dist = [[float('inf')] * V for _ in range(V)]
# 자기 자신으로의 최단 경로는 항상 0
for i in range(V):
dist[i][i] = 0
# 그래프의 간선 정보를 행렬에 반영
for u in range(V):
for v in range(V):
if u != v and graph[u][v] != 0:
dist[u][v] = graph[u][v]
# 플로이드-와샬 알고리즘 수행
for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# 테스트용 그래프
graph = [
[0, 5, float('inf'), 10],
[float('inf'), 0, 3, float('inf')],
[float('inf'), float('inf'), 0, 1],
[float('inf'), float('inf'), float('inf'), 0]
]
# 플로이드-와샬 알고리즘 호출 및 결과 출력
result = floyd_warshall(graph)
for row in result:
print(row)
다익스트라 (Dijkstra) vs 플로이드-와샬 (Floyd-Warshall)
- 목적
- 다익스트라 알고리즘: 주어진 출발 노드에서 모든 다른 노드로의 최단 경로를 찾는 데 중점
- 플로이드-와샬 알고리즘: 그래프 내의 모든 노드 쌍 간의 최단 경로를 찾는 데 중점
- 알고리즘 유형
- 다익스트라 알고리즘: 그리디 알고리즘으로, 각 단계마다 가장 가까운 노드를 선택하여 최단 경로를 찾음
- 플로이드-와샬 알고리즘: 다이나믹 프로그래밍 기반으로, 모든 노드 쌍에 대한 최단 경로를 구하기 위해 최적 부분 구조를 사용
- 음수 가중치
- 다익스트라 알고리즘: 음수 가중치를 갖는 간선이 있으면 제대로 동작하지 않음
- 플로이드-와샬 알고리즘: 음수 가중치를 가진 간선이 있어도 처리 가능
- 시간 복잡도
- 다익스트라 알고리즘: 최악의 경우
O(V^2)의 시간 복잡도를 가지며, 힙을 사용하면O((V+E)logV) - 플로이드-와샬 알고리즘:
O(V^3)의 시간 복잡도
- 다익스트라 알고리즘: 최악의 경우
최소 신장 트리 (MST: Minimum Spanning Tree)
- 연결된 가중치 그래프에서 모든 노드를 포함하면서 간선의 가중치 합이 최소가 되는 트리
- 주어진 그래프 내에서 모든 노드를 연결하는 최소한의 비용으로 노드 간의 통신이나 연결을 할 때 유용
최소 신장 트리의 특징
- 간선의 수
- 최소 신장 트리는 모든 노드를 연결하면서 사이클이 없는 트리
- 따라서 노드의 개수가
n인 그래프의 최소 신장 트리는 반드시n - 1개의 간선을 가져야 함
- 가중치
- 최소 신장 트리의 간선 가중치의 합은 가능한 모든 신장 트리 중에서 가장 작음
의사 코드 - 크루스칼 알고리즘 (Kruskal)
- 신장 트리에서 하나 하나 간선을 더해가며 만드는 방법
- 각 반복마다 가장 적은 가중치를 가진 간선을 찾는 그리디 알고리즘과 비슷하다.
크루스칼(그래프):
mst = [] # 최소 신장 트리를 저장할 리스트
edges = [] # 간선들을 저장할 리스트
# 그래프의 간선들을 추출하여 edges 리스트에 저장
for 각 노드 u 에 대해:
for 각 연결된 노드 v 와 가중치 w 에 대해:
edges.append((u, v, w))
# 간선들을 가중치에 따라 정렬
edges.sort(key=lambda x: x[2])
parent = [i for i in range(그래프의 노드 개수)] # 각 노드의 부모 노드를 저장할 배열
# 두 집합을 합치는 함수
def union(u, v):
root_u = find(u)
root_v = find(v)
parent[root_v] = root_u
# 노드의 부모를 찾는 함수
def find(u):
while parent[u] != u:
u = parent[u]
return u
# 모든 간선을 확인하면서 최소 신장 트리를 구성
for 간선 (u, v, w) in edges:
if find(u) != find(v): # u와 v가 같은 집합에 속하지 않는다면
mst.append((u, v, w)) # 해당 간선을 mst에 추가
union(u, v) # u와 v를 하나의 집합으로 합침
반환 mst # 최소 신장 트리 반환
의사 코드 - 프림 알고리즘 (Prim)
- 그래프의 정점을 하나씩 추가해가며 최소 신장 트리를 만들어 나가는 알고리즘
시작 노드 선택 -> 트리에 인접한 간선 탐색 -> 노드 추가 및 간선 탐색 -> (반복)의 과정을 거침
프림(그래프):
mst = [] # 최소 신장 트리를 저장할 리스트
visited = [False] * 그래프의 노드 개수 # 방문한 노드를 표시하는 배열
heap = [] # 우선순위 큐를 표현할 리스트
시작노드를 우선순위 큐에 추가 # 아무 노드나 시작해도 됨
while heap가 비어있지 않을 때:
현재노드 = 우선순위 큐에서 가장 가중치가 작은 노드를 꺼냄
if 현재노드가 이미 방문한 노드라면:
continue
현재노드를 방문한 것으로 표시
if 현재노드의 부모노드가 존재한다면:
mst.append((부모노드, 현재노드, 현재노드와 부모노드 사이의 가중치))
현재노드와 연결된 모든 간선을 우선순위 큐에 추가
for 인접노드, 가중치 in 현재노드의 인접한 노드들:
if 인접노드가 이미 방문한 노드가 아니라면:
heap에 (인접노드, 가중치)를 추가
반환 mst # 최소 신장 트리 반환
