[Algorithm] DFS - 다익스트라(Dijkstra): 파이썬, 자바스크립트

다익스트라 알고리즘

• 깊이우선탐색 알고리즘(DFS) 중에 하나로 그래프 자료구조에서 최단거리, 최소기간을 구하는데 주로 사용되는 알고리즘이다.

• 우선순위 탐색을 하는 경우 많이 쓰인다.

  • 우선순위 탐색은 그래프에서 vertex를 탐색할 때 가중치에 따라 우선순위를 결정하여 탐색하는 것을 말한다.

  • 보통 [[1, 2, 4], [1, 3, 2], [2, 5, 3]] 이런식으로 그래프가 있다면

  • [w=시작, v=인접한 정점, w=가중치]로 구성되어 있다.

• 핵심은 거리를 계속 기록하며 검사하다가 이미 기존 거리보다 큰 vertex를 만났을 경우 검사하지 않는다는 것이다.

• 우선순위 탐색을 위해 파이썬에서는 주로 힙큐 자료구조를, 자바스크립트에서는 우선순위 큐를 구현해 사용한다.

파이썬 코드

edges = [[1, 2, 4], [1, 3, 2], [2, 5, 3], [3, 4, 1], [4, 5, 3], [4, 6, 5], [5, 7, 4], [6, 7, 5]]
g = collections.defaultdict(lambda: collections.defaultdict(int))

# 딕셔너리로 그래프를 만들어준다.
for u, v, w in edges:
    g[u][v] = w

• 딕셔너리로 그래프 구현
  

• 그래프 시각화
  

def dijkstra(g, start):
    q = [(0, start)]

    dists = collections.defaultdict(lambda: float('inf'))
    dists[start] = 0

    pprint(dists)

    while q:
        dist, u = heapq.heappop(q)

        # 기존 거리 보다 크면 검사X
        if dists[u] < dist:
            continue

        for v, weight in g[u].items():
        	# 기존 거리보다 작을 경우에만 힙큐에 추가
            if weight + dist < dists[v]:
                heapq.heappush(q, (weight + dist, v))
                dists[v] = weight + dist

    return dists

• dists 딕셔너리
  
  (pprint 모듈을 불러와 보기쉽게 dict를 출력할 수 있습니다.)

dijkstra 함수를 실행하면
7정점까지 가는데 최소 거리는 10인 것을 알 수 있습니다.

자바스크립트 코드

let edges = [[1, 2, 4], [1, 3, 2], [2, 5, 3], [3, 4, 1], [4, 5, 3], [4, 6, 5], [5, 7, 4], [6, 7, 5]]

let g = {}

for (let edge of edges) {
    let u = edge[0], v = edge[1], w = edge[2]
    if (!g[u]) {
        g[u] = {}
    }
    g[u][v] = w
}

console.log(g)

function dijkstra(g, start=1) {
    // [거리, 시작노드]
    let q = [[0, start]]

    console.log(q)

    // dists는 각 vertex까지의 거리를 기록하는 객체
    // dists에 있는 기존 거리보다 거리가 큰 vertex가 나오면 지나침
    let dists = {}
    for (let key in g) {
        dists[key] = Infinity
    }

    console.log(dists)

    // 출발 거리 초기화
    dists[start] = 0

    while(q.length > 0) {
        // 우선 순위 큐를 위한 정렬: 오름차순
        q.sort((a, b) => a[0] - b [0])

        // 가장 우선순위가 높은 항목 추출
        let [dist, u] = q.shift()

        // 기존 거리보다 크면 검사하지 않음: 할 필요 없음
        if(dists[u] < dist) {
            continue
        }

        // 해당 vertex로 갈 수 있는 모든 노드 검사 및 dists 갱신
        for (let v in g[u]) {
            let weight = g[u][v]
            // 기존 거리보다 작으면 우선순위 큐에 추가
            if(weight + dist < dists[v]) {
                q.push([weight + dist, v])
                dists[v] = weight + dist
            }
        }
    }

    return dists
}

const res = dijkstra(g, 1)
console.log(res)

• 자바스크립트는 콘솔을 찍어가며 코드를 구현해보니 이해가 좀 더 쉬웠다.
  

시간복잡도 & 공간복잡도

• 다익스트라 알고리즘의 시간복잡도는 우선선위 큐의 구현 방식에 따라 달라진다.

  • 여기서는 배열로 구현했기 때문에 각 노드를 큐에 넣고(삽입) 빼는(삭제) 데 O(V)의 시간이 걸리므로, 전체 시간 복잡도는 O(V^2)가 된다.

  • V는 정점(Vertex)의 수다.

• 공간복잡도는 그래프의 노드 수 V와 엣지 수 E에 비례한다.

  • 그래프를 인접 리스트로 표현한다면 공간 복잡도는 O(V + E)가 된다.

  • 거리를 저장하는 dists 배열이나 우선순위 큐 등 추가적인 공간이 필요하기 때문에 공간복잡도는 대략적으로 O(V)라고 할 수 있다.