파이썬 - 최단 경로(shortest path)

목차

-시작

-플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

-다익스트라 알고리즘(Dijkstra algorithm)

-벨먼-포드 알고리즘(Bellman-Ford algorithm)

-문제

시작

최단 경로 알고리즘은 graph가 주어 질 때 최단 경로를 찾는 방법입니다.

graph는 node와 edge로 구성된 집합입니다.

만약 위의 문장이 생소하다면 여기를 클릭해 주세요.  클릭

 

이전에 배운 BFS 또한 최단 거리 알고리즘이라 할 수 있습니다.

BFS는 weight가 없는(edge의 거리가 모두 1인) graph가 주어질 때 시작 node에서 모든 노드로 가는 최단 거리를 구하는 알고리즘이었습니다. 

BFS가 크리스털 클리어하지 않다면 여기를 클릭해 주세요.  클릭   

 

최단 경로 알고리즘에는 문제 상황에 따라 3가지로 분류됩니다.

• 단일-출발 최단 경로 문제 : 1개의 시작 node에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제입니다. 그림
• 단일-도착 최단 경로 문제 : 모든 node로부터 시작하여 마지막 node 1개에 가장 짧은 경로를 찾는 문제입니다. 단일-출발 문제를 조금만 수정하면 얻을 수 있는 알고리즘입니다. 그림
• 전체-쌍 최단 경로 문제 : 그래프 내의 모든 node끼리의 최단 경로를 찾는 문제입니다. 그냥 싹 다 찾는다는 말입니다. 그림

 

BFS의 경우에는 시작 node에 대한 모든 node의 최단거리를 구할 때 사용할 수 있습니다.

그렇기에 단일-출발 최단 경로 문제에 사용될 수 있습니다.

또한 구현을 조금만 변형하면 단일- 도착 최단 경로 문제를 해결할 수 있습니다.

마지막으로 모든 node를 시작 node로 하여 BFS를 진행하면 전체-쌍 최단 경로 문제를 해결할 수 있습니다.

 

뭐지? 그럼 BFS만 해면 다되니 공부 안 해도 되나?

그건 아닙니다.

graph에 모든 weight가 0보다 큰 정수일 때를 상상해 봅시다.

graph의 weight가 있더라도 BFS를 활용하면 모든 최단 경로 문제를 해결할 수 있습니다.

weight를 가상의 node와 weight가 1인 변경시킨 graph를 구현합니다.

그림

그리고 새로운 graph에 대해 BFS를 진행합니다.

위의 방식을 이용하면 BFS로도 해결이 가능합니다.

하지만 시간 복잡도의 측면에서 보면 이건 아니다 싶습니다.

BFS의 경우 시간 복잡도는 O(nodes**2)입니다.

weight의 수만큼 새로운 node들이 생성된 graph에 대한 시간 복잡도는 O( ( nodes + sum(weights))**2 )입니다.

weight가 크면 답도 없습니다. 

 

또한 weight가 음수면 어떻게 될까요?

벌써부터 뇌 정지가 옵니다.

음수의 경우에는 BFS사용 시 최단 경로를 얻지 못합니다.

 

결국 알고리즘을 공부하는 이유는 상황에 따라 적절한 알고리즘을 선택하여 문제를 해결하기 위함입니다.

이번 최단 경로 알고리즘도 같은 맥락입니다.

비록 시간이 무제한 일 때 모든 문제를 BFS로 해결할 수 있지만 더 디테일하게 들어갈 수 있도록 학습해 봅시다.

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

최단 경로 알고리즘 중 구현이 가장 간단한 알고리즘입니다.

플로이드-위셜 알고리즘을 수행하면 O(node**3)의 시간복잡도를 가지고 모든 시작점과 끝점에 대한 최단 경로를 구할 수 있습니다.

 

작동 방식은 대략적으로 이렇습니다.

플로이드-위셜 알고리즘은 임이의 시작점(s) 끝점(e)으로 가는 최단 경로를 얻기 위해 s와 e의 중간 지점 m을 활용합니다.

s ,e 그리고 m사이에는 아래와 같은 점화식을 만족합니다.

dp [s][e] = min( dp [s][m] + dp [e][m], dp [s][e] )

모든 중간 지점 m에 대한 최단 경로를 계산하고 이 중 가장 작은 값을 선택합니다.

 

노드 3개에 대해 for loop를 사용하기에 O(node**3)의 시간복잡도를 가집니다.

 

구현

dp = [ [float('inf') for _ in range(len(nodes))] for _ in range(len(nodes)) ]

for u, v in edges:
    dp[u][v] = weight(u,v)

for m in nodes:
    for s in nodes:
        for e in nondes:
            if dp[s][e] > dp[s][m] + dp[m][e]:
                dp[s][e] = dp[s][m] + dp[m][e]

 

다익스트라 알고리즘(Dijkstra algorithm)

다익스트라 알고리즘은 특정 노드 s에서 모든 점의 최단 경로를 찾는 알고리즘이다.이전에 학습했던 워셜 알고리즘과 달리 그리디 방법을 사용하여 구현에 따라 O(node**2)에서 O(n*logn)의 시간복잡도를 가진다.  

 

작동 방식은 대략적으로 이렇습니다.1. 최단 거리를 갱신하기 위한 테이블을 만듭니다.    table[i] = float('inf')이처럼 모든 테이블을 무한대로 초기화시킵니다.   table [시작] = 0 시작 노드에 대해 거리가  0 임을 기록합니다.   visited = set() 2. 시작 노드를 방문 처리하고 이웃한 노드에 대하여 table을 갱신합니다.   table [이웃 노드] = min(table [시작 노드] + weight(시작 노드, 이웃 노드), table [이웃 노드])    visited.add(시작 노드) 3. table에서 값이 가장 작고 visited에 없는 노드를 선택합니다.

4. 선택된 노드를 시작 노드로 생각하고 2를 진행합니다. 만약 3. 을 만족하는 노드가 없으면 종료합니다.

 

모든 노드를 한 번씩 탐색하는데 O(n)이 사용되고 table에서 가장 작은 노드를 찾는데 O(n)이 사용됩니다.

그래서 시간 복잡도는 O(n)입니다.

만약 table에서 가장 작은 노드를 찾기 위해 heap 자료구조를 사용한다면 O(logn)으로 줄어들어 전체 시간복잡도는 O(nlogn)입니다.

 

구현

table = [float('inf') for _ in range(number_of_nodes)]
table[start_node] = 0
visited = set()

while True:
    visited.add(start_node)
    for adj in ajds():
        table[adj] = min(table[adj], table[start_node] + weight(start_node, adj))
    next_node = find_min_node(table)
    if next_node == "empty":
        break
    else:
        start_node = next_node

 

문제

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

문제는 대략 이렇습니다.

1번 부터 N가지 Node가 존재합니다.

node들은 weight가 있는 양방향 edge로 구성되어 있습니다.

1번부터 출발하여 최단 거리가 K이하인 node의 수를 구하는 문제입니다.

 

문제를 읽고 드는 생각.

다익스트라 알고리즘을 이용하면 간단하게 해결 가능할듯합니다.

이 문제에서 얻을 만한 내용은 road를 사용하기 좋게 가공하는 패턴을 익히는 것입니다.

저의 경우 adjs = { i : [ [node, weight], [node, weight]  for i in range(1, N+1]}의 형식으로 가공하여 사용하였습니다.

각자 뇌정지가 안 되는 방식으로 구현하면 좋을 듯합니다.

def solution(N, road, K):
    adjs = {i: [] for i in range(1,N+1)}
    for node1, node2, weight in road:
        adjs[node1].append([node2, weight])
        adjs[node2].append([node1, weight])
    table = huristic_man(N, adjs)
    answer = 0
    for key, val in table.items():
        if val <= K:
            answer += 1
    return answer
    
    
def huristic_man(N, adjs):
    n = [1]
    visited = set()
    INF = float('inf')
    table = {i : INF  for i in range(1,N+1)}
    table[1] = 0
    while n:
        node = n.pop()
        visited.add(node)
        for adj, weight in adjs[node]:
            if adj not in visited:
                table[adj] = min(table[adj], table[node]+weight)
        mval = minval(table, visited)
        if mval != 'null':
            n.append(mval)  
    return table


def minval(table, visited):
    result_val = float('inf')
    result_key = 'null'
    for key, val in table.items():
        if result_val >= val and key not in visited:
            result_val = val
            result_key = key
    return result_key

https://programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

문제는 대략 이렇습니다.

특정 지점 까지 같이 가다가 따로 가는 경우에 대한 최단 거리를 구하는 문제입니다.

 

문제를 읽고 드는 생각

다익스트라를 이용하거나 플로이드 위셜 알고리즘을 이용하여 해결하면 될듯합니다.

위의 알고리즘을 이용하여 구한 최단 경로를 sp[start][end] table에 저장하였다고 생각해봅시다. 

그럼 정답은 sp[s][m] + sp[m][a] + sp[m][b]를 3중 루프를 돌며 최솟값을 찾으면 됩니다.