[알고리즘] 최단경로와 다익스트라 알고리즘, 다익스트라 구현, 최단경로와 플로이드

 

 

 

 

 

---

최단경로

• 보통 A에서 B로 가는 최소 비용을 의미
• 그래프로 표현. 각 지점은 노드, 도로는 간선.
• 다익스트라, 플로이드-워셜을 배울 예정.
• 지도 앱에서 광범위하게 사용

---

다익스트라 알고리즘

• 튜링상 수상 등, 위대한 아저씨: https://ko.wikipedia.org/wiki/에츠허르_데이크스트라
• 대표작은 다익스트라 알고리즘, 구조적 프로그래밍.
• 그 중에서 다익스트라 알고리즘을 배워보겠습니다.

다익스트라 설명 도표 (a-f 시간순, 출발지점 s, 각 노드의 숫자: 출발부터 해당 노드까지의 최소비용)

인접노드: 지금 노드에서 바로 갈 수 있는 노드

더 작은 비용을 가진 노드에서 부터 다시 검색하여 계산

출발점이 정해져있을때, 나머지 모든 노드에 다르는 최소 비용을 계산하는 알고리즘

1. 출발지를 s로 정하고, 다음과 같이 표시한다.
      (s,    t,     x,     y,     z  순)
거리 = [0,    inf,   inf,   inf,   inf] # 방문 안한 곳은 무한대(inf)를 넣고, 방문한 곳은 숫자 넣어줌
방문 = [True, False, False, False, False]

2. 갈 수 있는 노드들의 최소거리를 측정한다.
s->t: 10
s->y: 5
      (s,    t,     x,     y,     z  순)
거리 = [0,    10,    inf,   5,     inf]
방문 = [True, False, False, False, False]

3. 방문 안한 녀석들 중 가장 가까운 녀석인 y를 방문하고, 최소거리를 측정한다.
y->t: 3
y->x: 9
y->z: 2
      (s,    t,     x,     y,    z  순)
거리 = [0,    8,     14,    5,    7]
방문 = [True, False, False, True, False]

4. 방문 안한 녀석들 중 가장 가까운 녀석인 z를 방문하고, 최소거리를 측정한다.
z->x: 6
      (s,    t,     x,     y,    z  순)
거리 = [0,    8,     13,    5,    7]
방문 = [True, False, False, True, True]

5. 방문 안한 녀석들 중 가장 가까운 녀석인 t를 방문하고, 최소거리를 측정한다.
t->x: 1
t->y: 2
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, False, True, True]

6. 방문 안한 녀석들 중 가장 가까운 녀석인 x를 방문하고, 최소거리를 측정한다.
x->z: 4
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, True, True, True]

7. 방문 안한 노드가 없으므로 끝낸다.
      (s,    t,     x,    y,    z  순)
거리 = [0,    8,     9,    5,    7]
방문 = [True, True, True, True, True]

 

 

---

다익스트라 구현

다익스트라 구현 (1) - naive한 방법

 

testcase1.txt

6 11 #노드의 개수 6, 간선의 개수 11
1  #출발지(start)
1 2 2 #간선 11개들 시작 #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

 

import sys

from min_cost.dijkstra import dijkstra_naive, dijkstra_pq

with open('testcase1.txt') as f:
    sys.stdin = f
    # input: 파일의 한줄씩 읽음 
    input = sys.stdin.readline
    n, m = map(int, input().split())
    start = int(input())
    
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        # a에서 b까지의 비용이 c
        a, b, c = map(int, input().split())
        # 튜플 저장  - 인덱스:노드 (목적지, 비용)
        graph[a].append((b, c))
                                       
                 # 결과값의 0번째 요소 10억은 무시(0번째 값은 없으므로 inf이 나오는 것)
assert dijkstra_naive(graph, start) == [1000000000, 0, 2, 3, 1, 2, 4]

# 무한대에 10억 저장
INF = int(1e9)


def dijkstra_naive(graph, start):
    def get_smallest_node():
        min_value = INF
        idx = 0
        for i in range(1, N):
            # 방문한 적 없다면
            if dist[i] < min_value and not visited[i]:
                min_value = dist[i]
                idx = i
        return idx

    N = len(graph)
    visited = [False] * N
    dist = [INF] * N

    visited[start] = True
    dist[start] = 0
	
    # adj 인접 경로, d 비용(업데이트!)
    for adj, d in graph[start]:
        dist[adj] = d

    # N개의 노드 중 첫 노드는 이미 방문했으므로,
    # N-1번 수행하면 된다.
    for _ in range(N - 1):
        # 가장 가깝고 방문 안한 녀석을 고르고,
        cur = get_smallest_node()
        visited[cur] = True
        # 최단거리를 비교, 수정한다.
        for adj, d in graph[cur]:
            cost = dist[cur] + d
            if cost < dist[adj]:
                dist[adj] = cost

    # 최소값 배열 리턴
    return dist

 

다익스트라 구현 (2) - 이진탐색 이용

 

heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

print(heap)

# [10, 50, 20]

# 이미 생성해둔 리스트가 있다면 heapify 함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다.

heap2 = [50 ,10, 20]
heapq.heapify(heap2)

print(heap2)

# [10, 50, 20]

# heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그를 결괏값으로 리턴한다.

result = heapq.heappop(heap)

print(result)
print(heap)

# 10
# [20, 50]

import heapq


def dijkstra_pq(graph, start):
    N = len(graph)
    dist = [INF] * N

    q = []
    # 튜플일 경우 0번째 요소 기준으로 최소 힙 구조.
    # 첫 번째 방문 누적 비용은 0이다.
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q:
        # 누적 비용이 가장 작은 녀석을 꺼낸다.
        acc, cur = heapq.heappop(q)

        # 이미 답이 될 가망이 없다.
        if dist[cur] < acc:
            continue

        # 인접 노드를 차례대로 살펴보며 거리를 업데이트한다.
        for adj, d in graph[cur]:
            cost = acc + d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))

    return dist

우선순위  q를 min heap 으로 구현한것

import sys

from min_cost.dijkstra import dijkstra_naive, dijkstra_pq

with open('testcase1.txt') as f:
    sys.stdin = f
    input = sys.stdin.readline
    n, m = map(int, input().split())
    start = int(input())
    graph = [[] for _ in range(n + 1)]

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

assert dijkstra_naive(graph, start) == [1000000000, 0, 2, 3, 1, 2, 4]
assert dijkstra_pq(graph, start) == [1000000000, 0, 2, 3, 1, 2, 4]

 

 

시간복잡도 비교

#  V: 그래프의 길이 = 노드의 개수

• Naive: 이중 for 문이므로 O(N^2) = O(V^2) 
• PriorityQueue: O(ElogV)

---

다익스트라 예제

화성 탐사

(0,0) 에서 (n-1, n-1)로 가는 최소비용 계산

 

testcase_mars.txt

3
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4

 

test_mars.py

import sys

from min_cost.dijkstra import mars

# 테스트 파일 읽음
with open('testcase_mars.txt') as f:
    sys.stdin = f
    input = sys.stdin.readline

    T = int(input())
    for _ in range(T):
        N = int(input())
        graph = []
        for __ in range(N):
            graph.append(list(map(int, input().split())))

        print(mars(graph))

 

dijkstra.py

def mars(graph):
    # 상하좌우 row, col 별로 변화값 저장
    dr = [1, 0, -1, 0]
    dc = [0, 1, 0, -1]

    N = len(graph)
    # 거리를 저장하는 이차원 배열 (무한대 값으로 초기화)
    dist = [[INF] * N for _ in range(N)]

    q = []
    dist[0][0] = graph[0][0]
    heapq.heappush(q, (graph[0][0], 0, 0))  # 누적비용, row, col
    
    while q:
        # 누적 비용이 가장 작은 녀석을 꺼낸다.
        acc, r, c = heapq.heappop(q)

        # 이미 답이 될 가망이 없을 경우 or 이미 방문했을 경우 넘어감
        if dist[r][c] < acc:
            continue

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            # 상하좌우 값이 허용되는 범위 내에 있을 때
            if 0 <= nr < N and 0 <= nc < N:
                # 이 점까지 온 최솟값 + 새로운 곳으로 가는 비용
                cost = dist[r][c] + graph[nr][nc]
                # 기존에 가는 값보다 작다면 값을 업데이트하고 
                if cost < dist[nr][nc]:
                    dist[nr][nc] = cost
                    # 다음 출발지로 지정
                    heapq.heappush(q, (cost, nr, nc))

    return dist[N - 1][N - 1]

 

---

숨바꼭질

내가 술래와 얼마나 멀리 있게 되고, 그 거리와 똑같은 게 몇개인 지

가장 멀리 ➡️ 최단 거리가 가장 큰 녀석 ➡️ 다익스트라 사용

 

testcase_hide.txt

6 7 # 전체 노드의 개수 6 , 전체 간선의 개수 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2

 

test_hide.py

import sys
from collections import defaultdict

from min_cost.dijkstra import hide

with open('testcase_hide.txt') as f:
    sys.stdin = f
    input = sys.stdin.readline

    N, M = map(int, input().split())
    # 값을 지정하지 않으면 빈리스트로 초기화
    graph = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        # 그래프를 서로 연결시켜줌
        graph[a].append(b)
        graph[b].append(a)

    print(hide(graph))  # (4, 2, 3)

 

dijkstra.py

def hide(graph):
    N = len(graph)
    dist = [INF for _ in range(N + 1)]  # 1번 ~ N번까지

    q = []
    dist[0] = dist[1] = 0
    heapq.heappush(q, (0, 1))
    while q:
        acc, cur = heapq.heappop(q)
        if dist[cur] < acc:
            continue

        for adj in graph[cur]:
            # 최소비용 -> 몇번 이동 -> +1
            cost = acc + 1
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))
    
    # 0번째는 INF(무한대)이므로 1번째부터 세서, 최댓값 구함
    max_dist = max(dist[1:])
    # 돌면서 최대값과 같은 경우에만 1을 기록하여 더함 -> 최대거리인 것들의 개수가 나옴
    cnt = sum([1 for idx in range(1, N + 1) if dist[idx] == max_dist])

           # index 함수는 배열에서 중복 값이 여러개 있을때 가장 작은 인덱스를 반환함
    return dist.index(max_dist), max_dist, cnt

 

---

다이익스트라는 출발점이 고정되어있을 때, 나머지 노드에 이르는 최솟값

플로이드는 모든 노드에서 서로다른 모든 노드에 이르는 최솟값

 

플로이드-워셜

• 다익스트라: 출발점을 정했을 때 다른 노드에 이르는 최단거리.
• 플로이드-워셜: 모든 지점에서 다른 모든 지점까지 최단거리.
• 자기자신으로 가는 비용은 0
• 직접 연결되어있지 않은 경로는 무한대.

점화식

D ab: a에서 b로 가는 최소 비용

D ab는 은 a에서 b로 다이렉트로 가는법 , a에서 k, k에서 b를 거쳐 가는것을 합친 것 둘 중 하나(둘 중 최솟값)

 

 

다익스트라와 달리 플로이드는 경로가 음수도 허용됨.

 

자기 자신으로 가는 것은 모두 0. k=0 : 중간에 거쳐가는 점이 없을 때. k=1: 1을 거쳐 갈때, k=2: 2를 거쳐 갈 때 ...

 

 

구현

 

testcase_fw.txt

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

 

test_fw.py

import sys
from collections import defaultdict
from pprint import pprint

from min_cost.floyd_warshall import floyd_warshall

with open('testcase_fw.txt') as f:
    sys.stdin = f
    input = sys.stdin.readline

    N = int(input())
    M = int(input())

    graph = defaultdict(list)
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))

    pprint(floyd_warshall(graph))

 

floyd_warshall.py

INF = int(1e9)


def floyd_warshall(graph):
    N = len(graph)
    # 전부 무한대로 초기화
    dist = [[INF] * (N + 1) for _ in range(N + 1)]

    for idx in range(1, N + 1):
        # 자기 자신으로 가는 경우는 0
        dist[idx][idx] = 0

    for start, adjs in graph.items():
        for adj, d in adjs:
            dist[start][adj] = d
    # 여기까지. 다이렉트로 가는 경우(k=0) 업데이트.

    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                # a에서 b까지의 최소거리는: 다이렉트로 가는 기존 값, k라는 점을 거쳐가는 값 중 최솟값
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    return dist

 

시간 복잡도는 O(V^3)으로 빠르다고 할 수는 없지만,

모든 정점에서 다른 모든 정점에 이르는 최소비용을 구할 수 있으므로, 간간이 쓰이긴 한다.

다익스트라 만큼 자주 쓰이는 알고리즘은 아니지만, 전체 개수가 500개 정도라면 쓸만한 알고리즘이다. 

---

플로이드

https://www.acmicpc.net/problem/11404

5 # 노드가 5개
14 # 간선이 14개
1 2 2 # 1에서 2로 가는 비용은 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

 

testcase_floyd.py

with open('testcase_floyd.txt') as f:
    INF = int(1e9)
    sys.stdin = f
    input = sys.stdin.readline

    # 노드의 개수
    N = int(input())
    # 간선의 개수
    M = int(input())

    # 무한대로 초기화
    dist = [[INF] * (N + 1) for _ in range(N + 1)]

    # 자기 자신으로 가는 것은 0으로 초기화
    for i in range(1, N + 1):
        dist[i][i] = 0

    for _ in range(M):
        # 바로바로 입력 받음
        a, b, c = map(int, input().split())
        if c < dist[a][b]:
            dist[a][b] = c
    # 여기까지 다이렉트 경로들은 모두 업데이트

    # 플로이드 워셔
    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    for row in dist[1:]:
        # 무한대일 경우에는 0으로 출력
        print(' '.join([str(el) if el != INF else '0' for el in row[1:]]))

test_fw.py

---

정확한 순위

testcase_rank.txt

6 6 #노드가 6개, 간선이 6개
1 5 # 1에서 5를 갈 수 있다. (doable)
3 4
4 2
4 6
5 2
5 4

내가 다른 지점으로 갈 수 있으면 나보다 아래 있는 것들,

나한테 올 수있는 것들은 내 위에 있는 것들.

➡️ 나한테 오는 것들의 개수 + 내가 가는 것들의 개수 ➡️  전체 개수 ➡️  나의 순위 알 수 있다.

 

test_fw.py

with open('testcase_rank.txt') as f:
    print("*" * 80, f.name)
    INF = int(1e9)
    sys.stdin = f
    input = sys.stdin.readline

    N, M = map(int, input().split())
    dist = [[INF] * (N + 1) for _ in range(N + 1)]

    for idx in range(1, N + 1):
        # 나 자신에게 가는 것은 0 처리
        dist[idx][idx] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        # 갈 수 있다면 1로 표시
        dist[a][b] = 1

    #플로이드 워셔 알고리즘
    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    result = 0
    for cur in range(1, N + 1):
        cnt = 0
        # 현재 노드(cur)를 기준으로,
        # 다른 노드(node)로 갈 방법이 있는지 센다.
        for node in range(1, N + 1):
            # 내가 갈 수 있거나 or 나한테 올 수 있는 지 체크
            if dist[cur][node] != INF or dist[node][cur] != INF:
                cnt += 1
        # 모든 노드에 대해 갈 수 있다면 순위를 아는 것.
        if cnt == N:
            result += 1
    print(result)