[Python] Shortest Path Algorithm

Dijkstra Algorithm

• 특정 출발지에서 다른 모든 지점까지의 최단경로를 계산하는 알고리즘

# Baseline Code [1]의 시간복잡도 : O(V^2), V는 노드 수
import sys

INF = int(1e9)

# 노드의 개수, 간선의 개수를 입력받습니다.
n, m = map(int, sys.stdin.readline().split())

# 시작 노드를 입력받습니다.
start = int(sys.stdin.readline().rstrip())

# 각 노드에 연결되어 있는 노드에 대한 정보 초기화, (노드번호, 비용)
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

# 최단 거리 테이블
distance = [INF] * (n+1)

# 모든 간선 정보를 입력받습니다.
for _ in range(m):

    # a에서 b로가는 비용
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b,c))

# 다익스트라 알고리즘
def dijkstra(start):

    # 시작 노드 방문처리
    visited[start] = True

    # 시작 노드 거리 0
    distance[start] = 0

    # 시작 노드의 이웃 노드 정보 갱신
    for neighbor in graph[start]:

        distance[neighbor[0]] = neighbor[1]
    
    # 시작 노드를 제외하고 n-1번 반복
    for _ in range(n-1):

        # 가장 작은 값을 가지는 노드 획득
        now = get_smallest_node()

        # 해당 노드 방문처리
        visited[now] = True

        # 해당 노드의 이웃들에 대해 조사
        for neighbor in graph[now]:

            cost = distance[now] + neighbor[1]
            # 현재노드를 거쳐가는게 더 빠르다면 갱신합니다
            if distance[now] + neighbor[1] < distance[neighbor[0]]:

                distance[neighbor[0]] = cost
    
# 가장 작은 거리 값을 반환하는 함수
def get_smallest_node():

    # 최소값 초기화
    min_val = INF
    
    for i in range(1, n+1):

        if distance[i] < min_val and not visited[i]:

            min_val = distance[i]
            index = i
    
    return index

# 다익스트라 알고리즘 실행
dijkstra(start)

# 각 노드까지 가는 거리 출력
for i in range(1, n+1):

    if distance[i] == INF:

        print('INF')
    
    else:

        print(distance[i])

# Baseline Code [2]의 시간복잡도 : O(ElogV), V는 노드 수, E는 간선 수
import sys
import heapq

INF = int(1e9)

# 노드의 개수, 간선의 개수를 입력받습니다.
n, m = map(int, sys.stdin.readline().split())

# 시작 노드를 입력받습니다.
start = int(sys.stdin.readline().rstrip())

# 각 노드에 연결되어 있는 노드에 대한 정보 초기화, (노드번호, 비용)
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

# 최단 거리 테이블
distance = [INF] * (n+1)

# 모든 간선 정보를 입력받습니다.
for _ in range(m):

    # a에서 b로가는 비용
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b,c))

def Dijkstra(start):
	
    # 우선순위 큐 생성
	q = []
    
    # 출발지 거리 초기화
   	distance[start] = 0
    
    # 우선순위 큐에 출발지 입력, 첫 번째 원소인 거리 순서로 정렬된다.
    heapq.heappush(q, (0, start))
    
    # 큐가 끝날 때 까지 반복
    while q:
    
    	dist, cur = heapq.heappop(q)
        
        if dist > distance[cur]:
        	
            continue
            
        for neighbor in graph[cur]:
        
        	cost = dist + neighbor[1]
            
            if cost < distance[neighbor[0]]:
            
            	distance[neighbor[0]] = cost
                
                heapq.heappush(q, (cost, neighbor[0]))
 
# 각 노드까지 가는 거리 출력
for i in range(1, n+1):

    if distance[i] == INF:

        print('INF')
    
    else:

        print(distance[i])

Floyd-Warshall Algorithm

• 모든 노드에서 다른 모든 노드까지의 최단경로를 계산하는 알고리즘

# Baseline Code 시간복잡도 : O(V^3), V는 노드 수
import sys

INF = int(1e9)

n = int(sys.stdin.readline().rstrip()) # 노드의 수
m = int(sys.stdin.readline().rstrip()) # 간선의 수

# 그래프 초기화
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 = map(int, input().split())
    graph[a][b] = c

# Floyd-Warshall Algorithm
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(0, end=' ')
        else:
            print(graph[a][b], end=' ')
    print()