[정글 WEEK03_알고리즘] 개발 일지 - 최단 경로 알고리즘

📍 한 정점 → 모든 정점 탐색

    1. 다익스트라(Dijkstra)

    한 지점에서 다른 모든 지점까지의 최단 경로를 계산하는데, 양의 가중치 간선만 허용하는 알고리즘

    방향이 있는 그래프에서 '노드와 간선의 개수가 모두 많은' 경우 사용

   💡핵심 아이디어:  단계마다 '방문하지 않은 노드' 중에서 '가장 비용이 적은' 노드를 선택한 뒤에,

                                     그 노드를 거쳐 가는 경우를 확인해서 최단 거리 갱신

출처: https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

    빠르게 최소 거리 노드를 선택하기 위해서 우선순위 큐를,

    특정 노드의 인접 노드들을 확인하는 연산이 반복되므로 최단 거리 테이블은 인접리스트 사용

   

    V번 각 노드의 최단 거리를 결정할 때,

    → 매번 heapq.heappop()(O(logV))으로 가장 가까운 노드 하나를 꺼내므로 O(VlogV)

    E개의 간선마다

    → 특정 노드에서 인접한 노드를 확인하고 갱신되면 heappush()(O(logV))로 큐에 넣으므로 O(ElogV)

    보통 노드 수보다 간선 수가 훨씬 많으므로 O(VlogV) + O(ElogV) = O(ElogV)로 간주 

    따라서, 시간복잡도는 O(ElogV) 

 

   ⌨️ 구현

from heapq import heappop, heappush

def dijkstra(graph, start, end=None):
    p_q = [(0, start)]
    seen = set()
    
    n = len(graph)
    distance = [float('inf')] * n
    prev = [None] * n # 경로 추적용
    distance[start] = 0

    while p_q:
        _, now = heappop(p_q)
        if now in seen:
            continue
        seen.add(now)
        
        for next, weight in graph[now]:
            if distance[now] + weight < distance[next]:
                distance[next] = distance[now] + weight
                prev[next] = now 
                heappush(p_q, (distance[next], next))
                
    if end:
    	path = []
        current = end
        while current is not None:
            path.append(current)
            current = prev[current]
        path.reverse()
        
        return distance[end], path
    
    return distance

 

  2. 벨만 - 포드(Bellman-Ford)

   다익스트라와는 달리 음의 가중치 간선도 허용하는 것이 가장 큰 특징

   단, 음의 사이클은 비허용

   다익스트라보다 느리지만, 음의 간선이 있다면 필수적인 알고리즘

 

  💡핵심 아이디어:

       V-1번 모든 간선을 순회하며 거리 갱신 반복

       이후 한 번 더 검사하여 거리 갱신이 가능하면 → 음의 사이클 존재하는 것!

 

   매 간선마다 갱신을 시도하므로 시간복잡도는 O(V * E)
   

 

📍 모든 정점 → 모든 정점 탐색

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

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

  '노드의 개수가 적은' 가중치 방향 그래프의 경우 사용

출처: https://commons.wikimedia.org/wiki/Category:Floyd-Warshall_algorithm?uselang=ko

 

  DP를 이용해서 단계마다 '거쳐가는 노드'를 기준으로 최단 거리 테이블 갱신

  최단 거리 테이블은 모든 정점 간의 거리 정보를 다뤄야 하므로 인접 행렬 이용

  → 모든 노드에 대해서 다른 노드로 가는 최소 비용을 V^2 크기의 2차원 리스트에 저장한 뒤 해당 비용을 갱신해서 최단 거리 계산 

 

  음의 가중치 간선 허용

  단, 음의 사이클은 비허용 → 계속 돌아서 더 짧은 경로를 만들 수 있으니까 '최단 거리'라는 개념이 무의미해짐

 

  💡 핵심 아이디어: "중간에 특정 노드 k를 거쳐서 가면 더 짧은 경로가 될 수 있을까?"

                                   ➡️ 기존에 알고 있던 dist[i][j]보다 dist[i][k] + dist[k][j]가 짧다면 그걸로 갱신!

점화식: dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])

 

   3중 for문으로 i, j, k 정점을 확인하므로, 시간복잡도는 O(V^3)

   

   ⌨️ 구현 

INF = int(1e9) # 무한

vertex = int(input())
edge = int(input())

graph = [[INF] * (vertex + 1) for _ in range(vertex + 1)] # 모든 정점 간 비용을 무한으로 초기화

# 자기 자신에서 출발해서 자기 자신으로 도착하는 비용 처리
for a in range(1, vertex + 1):
    for b in range(1, vertex + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 비용 처리
for _ in range(edge):
    a, b, c = map(int, input().split())
    graph[a][b] = c
    
# 점화식에 따라 플로리드 워셜 알고리즘 수행
for k in range(1, vertex + 1): # 중간 노드
    for i in range(1, vertex + 1): # 출발 노드
        for j in range(1, vertex + 1): # 도착 노드
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
            
for a in range(1, vertext + 1):
    for b in range(1, vertex + 1):
        if graph[a][b] == INF:
            print("Unreachable", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

 

 

📍 한 정점 → 한 정점 탐색

   1. A* (휴리스틱)

   최단 거리 + 추정 거리(휴리스틱)를 더한 값을 기준으로 탐색 우선순위를 정함

   실제 거리와 예상 거리를 조합하여 목표 지점까지 빠르게 도달하도록 유도

   휴리스틱이 정확할수록 효율적으로 작동하지만, 잘못된 추정은 성능 저하 유발 가능

 

   2. BFS (비가중치 그래프)

   가중치가 없는 그래프에서 최단 경로를 찾기에 적합

   큐를 사용해서 한 레벨씩 차례로 탐색하며, 가장 먼저 도착한 경로를 최단 경로로 선택

   방문 여부를 기록해 중복 탐색 방지

   3. DFS + Pruning(가지치기)

   가능한 경로를 깊이 우선으로 탐색하고, 조건에 맞지 않으면 조기에 종료

   탐색 중간에 불필요한 경로를 잘라내는 "가지치기"를 통해 효율을 높임

   '최소 조건 만족 경로 찾기' 등 제한 조건이나 특수 목적이 있는 경로 찾기에 자주 사용됨