728x90
다익스트라 알고리즘 (Dijkstra SAlgorithm)
- 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
- '음의 간선'이 없을 때 정상적으로 동작한다
- 그리디 알고리즘
- 힙(Heap) 자료구조를 사용하여 구현할 것이다
- 시간 복잡도 : O(ElogV)
> 원리
1. 출발 노드 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
5. 3, 4번을 반복
> Code with Python
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n + 1)] # 각 노드에 연결된 노드 정보
distance = [INF] * (n + 1) # 최단 거리 테이블
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[0]
if cost < distance[i[1]]:
distance[i[1]] = cost
heapq.heappush(q, (cost, i[1]))
dijkstra(start)
for i in range(1, n + 1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
- 2차원 리스트에 최단 거리 정보를 저장
- 다이나믹 프로그래밍
- 시간 복잡도 : O(N^3)
> Code with Python
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
for k in range(1, n + 1):
for a in range(1, n + 1):
for b in range(1, n + 1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
for a in range(1, n + 1):
for b in range(1, n + 1):
if graph[a][b] == INF:
print("INFINITY", end=' ')
else:
print(graph[a][b], end=' ')
print()
📚 참고서적 : 이것이 코딩테스트다 with 파이썬
728x90