최단경로 알고리즘 BFS, 다익스트라, 벨만-포드, 플로이드 와샬

최단 경로 문제는 그래프 사이에서 두 노드 사이의 가장 짧은 경로를 찾는 문제이다. 최단 경로 알고리즘에는

1. 너비 우선 탐색 BFS

2. 다익스트라 알고리즘

3. 벨만-포드 알고리즘

4. 플로이드-워셜 알고리즘

이 있다

 

그래프

그래프는 상하위의 개념이 없이 각각의 노드와 노드들을 간선(edge)으로 연결한 자료구조이다.

지도 어플의 최단거리. 배송 최소이동거리, 지하철 노선도의 최단경로 등에서 활용되고 있다.

너비 우선 탐색

그래프에서 가까운 노드부터 탐색하는 알고리즘으로 간선의 길이가 없을 때 사용하는 알고리즘

a노드에서 인접한 노드 e, b, d, h로 이동하면서 탐색하는 알고리즘

def DFS(graph, root):
    open = [root]
    close = []

    while open:
        n = open.pop()
        close.append(n)
        if n not in close:
            close.append(n)
            open += graph[n] - set(close)
    return close

print(BFS(graph_list, root_node))

 

다익스트라

간선의 길이가 양수 일 때 사용하는 알고리즘이며 하나의 노드에서 다른 노드들까지 최단거리를 계산하는 알고리즘

1. 아직 선택되지 않은 노드 중에서 가장 간선의 길이가 짧은 노드를 선택한다.
2. 1번에서 선택된 노드와 연결된 다른 노드의 최단 거리를 갱신한다.
3. 탐색하지 않은 노드가 있으면 1번으로 돌아간다.

import heapq


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

    while queue:
        current_distance, current_destination = heapq.heappop(queue)

        if distances[current_destination] < current_distance:
            continue

        for new_destination, new_distance in graph[current_destination].items():
            distance = current_distance + new_distance
            if distance < distances[new_destination]:
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])

벨만-포드

간선의 길이가 음수일 때도 사용가능하다 사이클이 음의 값을 가지면 사용 불가능하다.

• 시작 노드에 대해서 거리를 0으로 초기화, 나머지 노드는 거리를 무한으로 설정
• 정점 수(n) -1 만큼 다음 과정을 반복
• 매 반복 마다 모든 간선 확인
• 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 거리 정보 갱신
• n-1번 반복 이후, n번째 반복에서도 거리 값이 갱신된다면 음수 순환이 존재

다익스트라는 방문하지 않는 노드 중에서 가장 가까운 노드를 방문했지만 벨만-포드는 매 반복마다 모든 간선을 확인한다는 것이 차이점이다.

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
INF = sys.maxsize

adj = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    adj[a].append((c, b))


def ford():
    ans = [INF] * (n + 1)
    ans[1] = 0
    for i in range(1, n):
        for j in range(1, n + 1):
            for c, b in adj[j]:
                if ans[j] == INF:
                    continue
                if ans[b] > c + ans[j]:
                    ans[b] = c + ans[j]
    for j in range(1, n + 1):
        for c, b in adj[j]:
            if ans[j] == INF:
                continue
            if ans[b] > ans[j] + c:
                print(-1)
                sys.exit()
    return ans


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

 

플로이드 와샬

모든 정점에서 다른 모든 정점으로의 최단거리를 계산할 때 사용하는 알고리즘

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