[알고리즘] 03. 그래프 탐색 - 2

15 Jan 2020 in Computer-Science

다양한 그래프 탐색 알고리즘의 특징을 살펴본다.

1. 최단 경로 알고리즘

두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘이다.

가중치 그래프에서는 간선의 가중치 합이 최소가 되도락 하는 경로를 찾는 것이 최단 경로를 찾는 것이다.

다익스트라 알고리즘

import heapq


def dijkstra(graph, start):
    dis = {node: float('inf') for node in graph}
    dis[start] = 0
    load = []
    heapq.heappush(load, [0, start])

    while load:
        new_dis, new = heapq.heappop(load)
        if new_dis <= dis[new]:
            for node, weight in graph[new].items():
                if dis[node] >= dis[new] + weight:
                    dis[node] = dis[new] + weight
                    heapq.heappush(load, [dis[node], node])
    return dis

그래프 내의 특정 노드 A 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제를 풀때 사용한다.

선택한 노드 A와 다른 노드와의 거리를 inf로 초기화한다.
선택한 노드 A와 연결된 노드와의 거리를 구하고 업데이트한다.
업데이트한 값중 최소값을 가진 노드(B)를 선택한다.
3에서 선택한 노드(B)와 연결된 노드와의 거리중 최소값을 가진 노드(C)를 구하고, A에서 B까지의 거리와 B에서 C까지의 거리를 더한 값을 업데이트한다.
3~4의 과정을 반복하여 inf값이 없을때까지 반복한다.