Shortest Path (최단경로 알고리즘)

In [1]:

from IPython.core.display import display, HTML

display(HTML("<style>.container { width:100% !important; }</style>"))

View Source

Shortest Path Algorithm (최단경로 알고리즘)¶

Objective¶

1. 최단경로 알고리즘 정의 및 특징
2. Dijkstra Algorithm
3. Floyd-Warshall Algoritm
4. 최단경로 알고리즘 예시 문제

1. 최단경로 알고리즘¶

1-1. 최단경로 알고리즘 정의¶

• 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘 을 의미합니다.
• 각 지점은 그래프에서 노드로 표현
• 지점 간 연결된 도로는 그래프에서 간선으로 표현

1-2. 최단경로 알고리즘 종류¶

• Dijkstra Algorithm
• Floyd-Warshall Algorithm
• Bellman-Ford Algorithm

1-3. 최단경로 알고리즘 문제상황¶

• 한 지점에서 한 지점까지의 최단 경로
  • Dijkstra, Bellman-Ford (음의 간선이 있을 경우)
• 한 지점에서 다른 모든 지점까지의 최단 경로
  • Dijkstra, Bellman-Ford (음의 간선이 있을 경우)
• 모든 지점에서 다른 모든 지점까지의 치단 경로
  • Floyd-Warshall

2. Dijkstra Algorithm¶

• 특정한 노드 에서 다른 노드로 가는 각각의 최단 경로를 계산
• '음의 간선' 이 없을때 동작, 있을 경우 Bellman-Ford 사용
• 매 상황에서 가장 비용이 적은 노드를 선택한다는 점에서 그리기 알고리즘 으로 분류

2-1. Dijkstra Algorithm 의 동작¶

1. 출발 노드를 설정
2. 최단 거리 테이블 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 해당 노드를 거쳐 다른 노드를 가는 비용을 계산하여 테이블을 갱신
5. 3~4 반복

2-2. Dijkstra Algorithm 구현 (Naive Version)¶

• $O(V^{2})$ 노드의 개수가 5000개 이하라면 가능
• 최단거리가 가장 짧은 노드를 선형탐색(V), 그 노드랑 연결된 노들들(V)을 확인.

In [12]:

# input

# 노드와 간선 갯수 
node, edge = map(int, input().split(' '))

# 시작점
start = int(input())

# 그래프 - adjacent list 형식 
adj_lst = [[] for _ in range(node+1)]

# 그래프 초기화 
for _ in range(0, edge):
    start_, end, cost = map(int, input().split(' '))
    adj_lst[start_].append([end, cost])

# 그래프 확인
for start_node, row in enumerate(adj_lst):
    print(f'start_node & [end_node,cost]: {start_node} -> {row}')

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
start_node & [end_node,cost]: 0 -> []
start_node & [end_node,cost]: 1 -> [[2, 2], [3, 5], [4, 1]]
start_node & [end_node,cost]: 2 -> [[3, 3], [4, 2]]
start_node & [end_node,cost]: 3 -> [[2, 3], [6, 5]]
start_node & [end_node,cost]: 4 -> [[3, 3], [5, 1]]
start_node & [end_node,cost]: 5 -> [[3, 1], [6, 2]]
start_node & [end_node,cost]: 6 -> []

In [33]:

def get_smallest_node(node, distance, visited):
    min_value = INF
    index = 0
    for i in range(1, node+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i 
    return index

def dijkstra_1(node, start, adj_lst):
    INF = int(1e9)
    
    visited = [False] * (node + 1)
    distance = [INF] * (node + 1)
    
    # 시작 노드 초기화
    distance[start] = 0
    visited[start] = True
    for j in adj_lst[start]:
        distance[j[0]] = j[1]
    
    # 시작노드를 제외한 나머지 node-1 개에 대해 탐색 -> 5개 -> 0번은 자연스레 제외됨
    for i in range(node-1):
        cur_node = get_smallest_node(node, distance, visited)
        visited[cur_node] = True
        for j in adj_lst[cur_node]:
            cost = distance[cur_node] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost 
    
    return distance

In [34]:

%%time
result = dijkstra_1(node, start, adj_lst)
print(result)

[1000000000, 0, 2, 3, 1, 2, 4]
CPU times: user 264 µs, sys: 122 µs, total: 386 µs
Wall time: 345 µs

2-3. Dijkstra Algorithm 구현 (Heap Version)¶

• Heap 자료구조를 활용한 Priority Queue 구현
• Heap 자료구조 설명 링크 참조
  • Lecture22
  • Lecture23
• Heap을 통한 $O(log{V})$ 탐색 : Heap 에 넣고 빼고 의 연산 vs $O(V)$ 탐색: 최단거리가 가장 짧은 노드를 선형탐색(V)
• $O(Elog{V})$
  • 우선순위 큐에서 꺼낸 노드 $O(log{V})$ 와 해당 연결된 다른 간선들의 거리를 확인 하는 횟수 -> 이때 연결될 수 있는 최대 간선의 개수는 $E$이므로 -> $O(Elog{V})$ 라 해석 가능
  • E개의 간선을 우선순위 큐에 넣었다가 모두 빼내는 연산과정과 유사 -> $O(Elog{E})$ -> 여기서 $E<V^2$ 이므로 -> $O(Elog{V^2})$ -> $O(Elog{V})$ 라고도 직관적으로 해석 가능

In [ ]:

# input

# 노드와 간선 갯수 
node, edge = map(int, input().split(' '))

# 시작점
start = int(input())

# 그래프 - adjacent list 형식 
adj_lst = [[] for _ in range(node+1)]

# 그래프 초기화 
for _ in range(0, edge):
    start_, end, cost = map(int, input().split(' '))
    adj_lst[start_].append([end, cost])

# 그래프 확인
for start_node, row in enumerate(adj_lst):
    print(f'start_node & [end_node,cost]: {start_node} -> {row}')

In [45]:

import heapq

def dijkstra_heap(node, start, adj_lst):
    INF = int(1e9)
    distance = [INF] * (node+1)
    
    q = []
    # heap 초기화 (0, 시작점)
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    # q 가 존재하면
    while q:
        cost, cur_node = heapq.heappop(q)
        
        # 이미 처리가 된 노드이면, 이미 최소값이면
        if distance[cur_node] < cost:
            continue
            
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for j in adj_lst[cur_node]:
            
            # 경유 과정 확인 비용
            total_cost = cost + j[1]
            
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[j[0]] > total_cost:
                distance[j[0]] = total_cost
                heapq.heappush(q, (total_cost, j[0]))
                
    return distance

In [46]:

%%time
result = dijkstra_heap(node, start, adj_lst)
print(result)

[1000000000, 0, 2, 3, 1, 2, 4]
CPU times: user 256 µs, sys: 121 µs, total: 377 µs
Wall time: 338 µs

3. Floyd-Warshall Algorithm¶

• 모든 노드에서 에서 다른 모든 노드 까지의 최단 경로를 모두 계산
• Dijkstra 와 마찬가지로 거쳐가는 노드를 기준으로 수행하지만, 매 단계 최단 거리를 갖는 노드를 찾는 과정이 없음
• 2차원 테이블에 최단 거리 정보 저장
• 노드의 개수가 N 개일 때 N 번 만큼의 단계를 반복하여, '점화식에 맞게' 값을 갱신하기에 다이나믹 알고리즘 으로 분류
• $D = min(D_{ab}, D_{ak} + D_{kb})$
• $O(N^3)$

In [48]:

# input

# 노드와 간선 갯수 
node, edge = map(int, input().split(' '))

# 그래프 - adjacent matrix 형식 
INF = int(1e9)

# 그래프 초기화
adj_matrix = [[INF] * (node+1) for _ in range(node+1)]
for i in range(1, node+1):
    adj_matrix[i][i] = 0

# 그래프 초기화 
for _ in range(0, edge):
    start_, end_, cost = map(int, input().split(' '))
    adj_matrix[start_][end_] = cost

# 그래프 확인
for row in adj_matrix:
    print(row)

4 7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2
[1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
[1000000000, 0, 4, 1000000000, 6]
[1000000000, 3, 0, 7, 1000000000]
[1000000000, 5, 1000000000, 0, 4]
[1000000000, 1000000000, 1000000000, 2, 0]

In [49]:

def floyd(node, adj_matrix):
    for k in range(1, node+1):
        for i in range(1, node+1):
            for j in range(1, node+1):
                if adj_matrix[i][j] > adj_matrix[i][k] + adj_matrix[k][j]:
                    adj_matrix[i][j] = adj_matrix[i][k] + adj_matrix[k][j]
    return adj_matrix

In [50]:

%%time
result = floyd(node, adj_matrix)
for row in result:
    print(row)

[1000000000, 1000000000, 1000000000, 1000000000, 1000000000]
[1000000000, 0, 4, 8, 6]
[1000000000, 3, 0, 7, 9]
[1000000000, 5, 9, 0, 4]
[1000000000, 7, 11, 2, 0]
CPU times: user 376 µs, sys: 159 µs, total: 535 µs
Wall time: 466 µs

4. 최단경로 알고리즘 예시 문제¶

4-1. 미래 도시¶

• https://github.com/ndb796/python-for-coding-test 참고
• floy-warshall
• 1 에서 K + K 에서 X

In [80]:

n, m = map(int, input().split())

INF = int(1e9)
graph = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n+1):
    graph[i][i] = 0
    
for _ in range(m):
    start_, end_ = map(int, input().split())
    graph[start_][end_] = 1
    graph[end_][start_] = 1
    
x, k = map(int, input().split())

5 7
1 2
1 3
1 4
2 4
3 4
3 5
4 5
4 5

In [81]:

def solution(n, graph, x, k):
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
                    
    distance = graph[1][k] + graph[k][x]
    
    if distance < INF:
        return distance
    else:
        return '-1'

print(solution(n, graph, x, k))

3

4-2. 전보¶

• https://github.com/ndb796/python-for-coding-test 참고
• Dijkstra

In [83]:

n, m, c = map(int, input().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    start_, end_, cost_ = map(int, input().split())
    graph[start_].append([end_, cost_])

3 2 1
1 2 4
1 3 2

In [117]:

import heapq

def dijkstra(n, start, graph):
    INF = int(1e9)
    distance = [INF] * (n+1)
    
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    
    while q:
        dis, cur_node = heapq.heappop(q)
        
        if distance[cur_node] < dis:
            continue
            
        for j in graph[cur_node]:
            cost = dis + j[1]
            if distance[j[0]] > cost:
                distance[j[0]] = cost
                heapq.heappush(q, (cost, j[0]))
                
    cnt = 0
    max_ = int(-1e9)
    for i in distance:
        if 0 < i < INF:
            cnt += 1
            max_ = max(i, max_)
        
    return cnt, max_

In [119]:

total_cities, time = dijkstra(n, start, graph)
print(total_cities, time)

2 4