파이썬 그래프, 트리 알고리즘

알고리즘 선택 (최단거리)

• 가중치가 없는 경우 - BFS
• 가중치가 있는 경우
  • 음의 가중치가 있을 때 - 벨만-포드
  • 음의 가중치가 없을 때 - 다익스트라
• 전체 쌍 최단 경로 - 플로이드-워셜 ( n ≤ 100 )

1. 벨만-포드 (Bellman-Ford Algorithm)

• 시간 복잡도: O(V * E)
• 모든 간선을 확인하며 최단 거리를 찾기 때문에 느리다.
• 음수 간선이 있어도 최단 거리를 찾을 수 있다.

import sys
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
    for i in range(n):
        for j in range(m):
            cur_node, next_node, cost = edges[j]
            if dist[cur_node] != INF and dist[next_node] > dist[cur_node] + cost:
                dist[next_node] = dist[cur_node] + cost
                if i == n - 1:
                    return 1
    return 0

negative_cycle = bf(1)

if negative_cycle:
    print('-1')
else:
    for i in range(2, n+1):
        if dist[i] == INF:
            print('-1')
        else:
            print(dist[i])

2. 다익스트라 (Dijkstra’s Algorithm)

• 시간 복잡도: O(E * log(E))
• 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구해나간다.
• 우선순위 큐 (heap) 사용

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)]
dist = [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))
    dist[start] = 0

    while q:
        weight, cur = heapq.heappop(q)
        if dist[cur] < weight:
            continue
        for g in graph[cur]:
            cost = weight + g[1]
            if cost < dist[g[0]]:
                dist[g[0]] = cost
                heapq.heappush(q, (cost, g[0]))

dijkstra(start)

for i in range(1, n + 1):
    if dist[i] == INF:
        print("INFINITY")
    else:
        print(dist[i])

3. 플로이드-워셜 (Floyd-Warshall Algorithm)

• 시간 복잡도: O(V^3) - 3중 for문
• 공간 복잡도: O(V^2) - 2차원 배열

n, m = map(int, input().split())
INF = int(1e9)
graph = [[0 if i == j else INF for i in range(n + 1)] for j in range(n + 1)]

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()