[다익스트라 알고리즘/ 플로이드 워셜 알고리즘] 구현코드

다익스트라 알고리즘 

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로

우선순위 큐를 이용한 구현법이 더 쉽고 시간복잡도도 낮음 O(E logV)

그리디 스러움

import heapq
import sys
 
input = sys.stdin.readline
INF = 1000000000  # 무한을 의미하는 10억 설정
 
# 노드의 개수, 간선의 개수
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())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 뜻
    graph[a].append((b, c))
print(graph)
 
 
def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단거리는 0으로 설정, 큐에 삽입 // 거리,노드번호 순
    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[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
 
 
 
 

 

 

 

 

플로이드 워셜 알고리즘

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산

시간 복잡도는 O(N^3)

 

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인

      a에서 b로 가는 최단 거리 보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다

 

 

점화식

import sys
 
input = sys.stdin.readline
INF = 1000000000  # 무한을 의미하는 10억 설정
 
# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 이차원 리스트를 만들고 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
 
# 자기 자신에서 자기 자신으로 가는 비용 0으로 초기화
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
    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])