1. 다익스트라(Dijkstra) 알고리즘이란

  • 음의 가중치가 없는 그래프의 한 정점에서 다른 정점까지의 최단 경로(거리)를 구하는 알고리즘이다.
  • 음의 가중치가 있을 때는 벨만-포드 알고리즘을 사용할 수 있다.
  • 가능한 모든 노드쌍의 최단 거리를 구할 때는 플로이드-워셜 알고리즘을 사용한다.
  • BFS를 기본으로 한다.

 

2. 다익스트라 알고리즘 동작 방식

  1. 출발 노드로부터 각 노드까지 최단 경로를 저장할 배열 distance[v]를 초기화하고, 출발 노드의 인덱스에는 0, 다른 노드에는 매우 큰 값을 저장한다(무한에 근접하도록 distance의 원소 타입의 최댓값으로 설정하면 된다).
  2. 현재 노드를 뜻하는 노드 A에 출발 노드 번호를 저장한다.
  3. A로부터 갈 수 있는 임의의 노드 B에 대해, A까지 최단거리(distance[A]) + A에서 B까지의 거리(graph[A][B])와 기존에 계산한 B까지의 최단거리(distance[B])를 비교한다. (min(distance[A]+graph[A][B], distance[B])) INF와 비교할 경우 무조건 전자가 작다.
  4. 만약 전자가 더 작다면, 즉 더 짧은 경로일 경우 distance[B]를 갱신한다.
  5. A의 모든 인접 노드에 대해 이 작업을 수행한다.
  6. 모든 인접 노드에 대해 위 작업을 마쳤으면, A를 '방문 완료'로 처리하여 중복 탐색을 방지한다.
  7. '미방문' 상태인 모든 노드들 중, 출발점으로부터 거리가 가장 짧은 노드를 하나 골라서 그 노드를 A에 저장한다.
  8. 도착 노드가 '방문 완료' 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7을 반복한다.

이 작업을 마친 뒤, 도착 노드에 저장된 값(distance[end])이 바로 A로부터의 최단 거리이다. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미한다.

 

 

3. 구현(파이썬)

3.1 단순한 방식

def dijkstra(start, n):
    infos = [[1, 2, 2], [1, 3, 1], [2, 4, 1], [2, 5, 2], [3, 4, 3], [4, 5, 1], [5, 6, 1]]
    INF = 10e9
    distance = [INF] * (n + 1)
    graph = [[] for i in range(n + 1)]
    visited = [False] * (n + 1)  
	
    for v, w, u in infos:
        graph[v].append((w, u))
        
    for v, w in graph[start]:
        distance[v] = w

    def get_smallest_node():
        smallest_value = INF
		index = 1
        for i in range(1, n+1):
            if distance[i] < smallest_value and not visited[i]:
                smallest_value = distance[i]
                index = 0
        return index
        
        
    for _ in range(n-1):
        now = get_smallest_node()
        visited[now] = True
        for child in graph[now]:
            c_node = child[0]
            cost = distance[now] + child[1]
            if cost < distance[c_node]:
                distance[c_node] = cost

이 경우 시간복잡도는 \(O(v^2)\)이다.

 

 3.2 우선순위큐 이용

from collections import defaultdict
import heapq

infos = [[1, 2, 2], [1, 3, 1], [2, 4, 1], [2, 5, 2], [3, 4, 3], [4, 5, 1], [5, 6, 1]]
INF = 10e9
distance = defaultdict(int)
graph = defaultdict(list)

Q = []

for u, v, w in infos:
    graph[u].append([v, w])
 
Q.append((0, start))

while Q:
    current_cost, current_node = heapq.heappop(Q)
    if  distance[current_node] < current_cost:
        continue
    for child in graph[current_node]:
        child_node = child[0]
        child_cost = child[1]
        alt_cost = current_cost + child_cost
        if alt_cost < distance[child_node]:
            heapq.heappush(Q, (alt_cost, child_node))

print(distance)

 

※ 우선순위 큐를 활용한 다익스트라 알고리즘의 시간복잡도

우선순위 큐를 사용할 경우 위 동작방식 7번에서 시간복잡도를 크게 줄일 수 있다.

우선순위 큐를 사용하면 한번 처리된 노드는 더이상 처리되지 않는다. 즉 노드를 하나씩 꺼내 검사하는 반복문(while문)은 노드의 개수 V 이상의 횟수로는 반복되지 않는다. 또한 V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인한다. 따라서 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 총 최대 간선의 개수 E만큼 연산이 수행될 수 있다. 일반적으로 힙연산의 시간복잡도는 \(O(logn)\)이고 \(O(logE)\)를 E개의 원소에 대하여 반복하는 것으로 볼 수 있으므로 시간복잡도는 \(O(ElogE)\)로 표현할 수 있다. 

이때 중복 간선을 포함하지 않는 경우, E는 항상 V의 제곱보다 작다. 왜나하면, 모든 노드끼리 서로 다 연결되어 있다고 했을 때 간선의 개수를 약 \(V^2\)으로 볼 수 있고 항상 E는 \(V^2\)이하이기 때문이다.

\(O(ElogE)\) <= \(O(ElogV^2)\)이고, \(O(ElogV^2)\)는 \(O(2*ElogV)\)이므로 \(O(ElogV)\)로 표현할 수 있다.

 

그래프 탐색 알고리즘 중 DFS에 이어 BFS에 대해 포스팅한다.

 

DFS(깊이 우선 탐색) 알고리즘

1. DFS 알고리즘이란 그래프 탐색 알고리즘의 한 종류 그래프 탐색이란 한 정점으로부터 시작하여 다른 정점을 차례대로 모두 한번씩 방문하는 것 DFS는 Depth First Search의 약자로서, 임의의 정점에

heero.tistory.com

 

1. BFS(너비 우선 탐색) 알고리즘이란?

  • 그래프 탐색 알고리즘의 한 종류
  • 그래프 탐색이란 한 정점으로부터 시작하여 다른 정점을 차례대로 모두 한번씩 방문하는 것
  • DFS가 임의의 정점에서 시작하여 다른 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이라면
  • BFS는 임의의 정점에서 시작하여 다음 레벨로 진입하기 전 인접한 분기를 모두 탐색하는 방법

2. BFS의 특징

  • 깊게 탐색하기 전에 넓게 탐색
  • BFS는 재귀로 구현할 수 없음
  • 방문한 노드를 저장하고 차례대로 꺼내면서 탐색하므로 큐(선입선출)를 사용하여 구현함

3. BFS의 장점

  • 가장 먼저 구한 해가 최단 경로임을 보장
  • 최단 경로가 존재한다면 특정 경로의 길이가 무한이라도 최단 경로를 찾을 수 있음

4. BFS의 단점

  • 큐에 탐색할 노드를 저장하므로 저장공간이 많이 소요
  • 노드가 많을수록 효율이 떨어짐 

5. BFS를 써야 하는 문제

 1) 두 노드 사이의 최단 경로 구하기 또는 임의의 경로 구하기

 2) 검색 대상의 규모가 크지 않은 경우, 검색 대상이 시작 지점으로부터 멀지 않은 경우

 3) 대상을 검색해야 하는 경우(조건을 만족하는 순회에 초점을 둔 DFS보다 유리)

 

6. 구현

스택과 재귀 두가지 방법으로 구현할 수 있었던 DFS와 달리 BFS는 큐를 사용한 반복구조로 구현하여야만 한다.

import collections
queue = collections.deque()
def bfs(start_node):
    visited = [start_node]
    queue.append(start_node)
    while queue:
        parent = queue.popleft()
        for child in graph[parent]:
            if child not in visited:
                queue.append(child)
                visited.append(child)
	return visited

참고)

collections 모듈에 구현된 deque자료형을 사용하였다.

리스트로도 구현할 수 있으나 큐의 연산을 구현하기 위해서는 pop(0)를 사용하여야 한다.

리스트의 pop연산은 리스트의 요소를 전부 복사하여야 하므로 시간 복잡도가 O(n)이다.

따라서 파이썬에서 queue를 성능저하 없이 사용하기 위해서는 deque자료형을 사용하고, 이 경우 O(1)에 연산이 가능하다.

1. DFS 알고리즘이란

  • 그래프 탐색 알고리즘의 한 종류
  • 그래프 탐색이란 한 정점으로부터 시작하여 다른 정점을 차례대로 모두 한번씩 방문하는 것
  • DFS는 Depth First Search의 약자로서, 임의의 정점에서 시작하여 다른 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다.

2. DFS의 특징

  • 모든 노드를 방문하고자 할 때 이 방법을 선택함
  • 넓게 탐색하기 전에 깊이 탐색함
  • 자기 자신을 호출하는 순환 알고리즘의 형태를 가짐
  • 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류임
  • 어떤 노드를 방문했는지 여부를 반드기 검사해야 무한 루프에 빠지는 것을 방지할 수 있음
  • 백트래킹에 사용됨

3. 장점

  • BFS(너비 우선 탐색)보다 구현이 간단함
  • 현재 경로 상 노드만 기억하면 되기 때문에 저장 공간이 적게 요구됨
  • 목표값이 깊은 곳에 있다면 빠르게 찾아낼 수 있음

4. 단점 

  • BFS에 비해 탐색 속도가 느림
  • 해가 존재하지 않는 경우 계속 탐색을 진행할 가능성이 있음, 임의의 종결 조건을 선언하여 탐색을 종료할 필요가 있음
  • 해가 도출되면 탐색을 종료하므로 최적의 해가 아닐 가능성이 있음

5. DFS를 사용해야 하는 문제

1) 경로의 특징을 저장해야 하는 문제 

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용(BFS는 경로의 특징을 가지지 못함)

 

2) 그래프의 크기가 정말 클 때

 

모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없음


6. 구현

1) 재귀로 구현

graph = {1: [2, 3, 4], 2: [5, 6], 3: [8],
         4: [8, 9],    5: [7],    6: [],
         7: [3],       8: [],     9: []}
 
def dfs_recursive(node, visited_path=[]):
    visited_path.append(node)
    for v in graph[node]:
        if v not in visited_path:
            recursive_dfs(v, visited_path)
    return visited_path
    
print(f'dfs_recursive path: {dfs_recursive(1)}')

 

2) 스택으로 구현

def dfs_stack(start_node):
    visited_path = []
    stack = [start_node]
    while stack:
        parent = stack.pop()
        if parent not in visited_path:
            visited_path.append(parent)
            for child in graph[parent]:
                stack.append(child)
    return visited_path
    
print(f'dfs_stack path: {dfs_stack(1)}')

인접 정점을 한번에 stack에 추가한다는 점에서 BFS처럼 보일 수 있으나 DFS가 맞다. 후입된 정점을 pop으로 선출하기 때문이다. 

+ Recent posts