TIL #22 : 최단 경로 알고리즘

📝 최단 경로 알고리즘

두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘
가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

📝 최단 경로 문제 종류

◾ 단일-출발 최단 경로 문제

특정 노드 v에서 출발하여 그래프 내의 모든 다른 노드들에 도착하는 가장 짧은 경로를 찾는 문제

◾ 단일-도착 최단 경로 문제

모든 노드들로부터 출발하여 그래프 내의 한 특정 노드 v로 도착하는 가장 짧은 경로를 찾는 문제
❗ 이 문제에서 그래프 내의 노드들을 거꾸로 뒤집으면 출발 최단 경로 문제로 바뀔 수 있음.

◾ 전체-쌍 최단 경로 문제

그래프 내의 모든 노드 쌍들 사이의 최단 경로를 찾는 문제

📌 다익스트라 알고리즘

• 위의 최단 경로 문제 종류 중에서 단일-출발 최단 경로 문제에 해당
• 첫 노드를 기준으로 연결되어 있는 노드들을 추가해 가며, 최단 거리를 갱신하는 기법
• 너비우선탐색(BFS)와 유사

def dijkstra(graph, start):
    queue =list()
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    queue.append([start,distance[start]])

    while queue:
        current_node, current_distance = queue.pop(0)

        if distance[current_node] < current_distance:
            continue

        for node, dist in graph[current_node].items():
            if (distance[current_node]+dist) < distance[node]:
                distance[node]=current_distance+dist
                queue = PriorityQueue(queue, [node, distance[node]])

    return distance

def PriorityQueue(queue, data):
    queue.append(data)
    return sorted(queue, key=lambda x: x[1])

1. 첫 노드을 기준으로 배열을 선언하여 첫 노드에서 각 노드까지의 거리를 저장

• 초기 : 첫 노드의 거리는 0, 나머지는 무한대로 저장
• 우선순위 큐에 첫 노드 데이터를 넣음.

2. 우선순위 큐에서 노드를 추출해 [노드, 첫 노드와의 거리]를 기반으로 인접한 노드와의 거리를 계산

3. 2번 과정을 우선순위 큐에서 추출할 노드가 없을 때까지 반복!