최단 경로

<최단 경로>

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

하나의 시작 정점에서 끝 정점까지의 최단 경로

1) 다익스트라(dijkstra) 알고리즘: 음의 가중치 X

# Priority queue

그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘

1. 시작 정점에서 각 정점까지의 최단 거리를 저장할 리스트 생성 (각 거리는 무한대로 초기화, 시작 정점 거리는 0)
2. 시작 정점과 거리를 우선순위 큐에 삽입
3. 우선순위 큐에서 가장 짧은 거리를 가진 정점 추출 → 인접한 정점 모두 확인 → 기존 거리보다 멀면 무시
4. 인접한 정점까지의 새로운 거리가 기존 저장된 거리보다 짧으면 → 거리 갱신 → 해당 정점과 갱신된 거리를 우선순위 큐에 삽입
5. 우선선위 큐가 모두 빌 때까지 반복

구분	다익스트라(Dijkstra)	프림(Prim)
목적	한 정점에서 시작해 다른 모든 정점까지의 최단 거리를 구함	그래프 전체에서 최소 신장 트리를 구함
결과물	시작 정점 → 각 정점까지의 최소 비용 경로	모든 정점을 연결하는 최소 비용의 트리
대상 그래프	방향 그래프 / 무방향 그래프 모두 가능, 음수 가중치 불가	무방향 그래프
동작 방식	시작 정점에서 출발	-

• 다익스트라는 “한 지점에서 다른 지점까지 가장 짧은 길을 찾는 것”
• 프림은 “모든 지점을 연결하는 최소 비용 네트워크를 만드는 것”

#다익스트라 알고리즘
import heapq

def dijkstra(V,graph,start):
    INF=float('inf')
    distance=[INF]*V
    distance[start]=0

    hq=[(0,start)] #(거리,정점)

    while hq:
        dist,u=heapq.heappop(hq)
        if dist>distance[u]:
            continue

        for v,w in graph[u]:
            if distance[v]>distance[u]+w:
                distance[v]=distance[u]+w
                heapq.heappush(hq,(distance[v],v))

    return distance

2) 벨만-포드(Bellman-Ford) 알고리즘: 음의 가중치 O

# DP (동적 프로그래밍)

시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

음수 가중치를 갖는 간선이 있는 그래프에서도 동작

1. 출발 노드를 설정 (각 거리는 무한대로 초기화, 시작 정점 거리는 0)
2. 최단 거리 테이블 초기화
3. 다음 과정을 N-1번 반복
   1. 전체 간선 E개를 하나씩 확인
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

• 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번 과정 한 번 더 수행
  • 이 때 최단 거리가 갱신된다면 음수 간선 순환이 존재

알고리즘	시간 복잡도	음수 가중치	음수 사이클 검출	비교
Dijkstra	O(ElogV)	❌	❌	매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 음수 간선이 없다면 최적의 해를 찾을 수 있음
Bellman-Ford	O(VE)	✅	✅	매번 모든 간선을 전부 확인 다익스트라 알고리즘에 비해 시간은 오래 걸리지만 음수 간선 순환 탐지 → 다익스트라 알고리즘에서 최적의 해를 항상 포함

#벨만-포드 알고리즘
def bellman_ford(V,edges,start):
    INF=float('inf')
    distance=[INF]*V
    distance[start]=0

    #(1) V-1번 반복
    for i in range(V-1):
        update=False
        for u,v,w in edges:
            if distance[u]!=INF and distance[v]>distance[u]+w:
                distance[v]=distance[u]+w
                update=True

        if not update:
            break

    #(2)음수 사이클 검사
    for u,v,w in edges:
        if distance[u]!=INF and distance[v]>distance[u]+w:
            return "음수 사이클 발생!"
    
    return distance

모든 정점들에 대한 최단 경로

3) 플로이드-워샬(Floyd-Warshall) 알고리즘

# DP (동적 프로그래밍)

모든 정점 쌍 간의 최단 경로를 구하는 알고리즘

→ 다익스트라, 벨만포드는 정점과 정점 간의 최단 경로를 구하는 알고리즘

음수 가중치가 있어도 정상적으로 동작 (음수 사이클은 X)

1. 초기화
   • dist[i][j] 행렬 준비
   • 자기 자신 정점은 0으로 설정
   • 간선이 존재하면 해당 가중치로, 없으면 ∞
2. 중간 정점 선택 (3중 for문)
   • 모든 정점을 중간에 거쳐갈 수 있는 정점 k를 차례로 선택
   • 각 i(출발 정점), j(도착 정점)에 대해 → dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
   • 즉, i→j 직접 가는 거리와 i→k→j 경유하는 거리 중 더 짧은 값 선택
3. 반복
   • k=0부터 V-1까지 모든 정점에 대해 2번 과정 반복
   • 반복이 끝나면 모든 정점 쌍 (i,j)에 대한 최단 거리 확정

#플로이드-워샬 알고리즘
def floyd_warshall(V,graph):
    #dist 배열 초기화(깊은 복사)
    dist=[row[:] for row in graph]

    for mid in range(V):
        for start in range(V):
            for end in range(V):
                if dist[start][end]>dist[start][mid]+dist[mid][end]:
                    dist[start][end]=dist[start][mid]+dist[mid][end]
    
    return dist