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

 

너비 우선 탐색 VS 다익스트라

너비 우선 탐색은 가장 적은 수의 구간을 가지는 경로를 찾는다. 다익스트라는 구간이 많더라도 더 빠른 경로를 찾을 수 있다.

너비 우선탐색이 가장 적은 수의 구간을 가지는 최단 구간을 찾는다면
다익스트라는 각 구간에 대해 숫자 혹은 가중치(weight)를 주고, 가중치의 합이 가장 작은 구간을 찾는다.

  • 균일 그래프(unweighted graph) : 너비우선탐색 적용

  • 가중 그래프(weighted graph) : 다익스트라 알고리즘 적용

  • 사이클(cycle) : 그래프가 어떤 정점에서 출발해서 한 바퀴 돌아 같은 정점에서 끝나는 경우. 사이클을 지날수록 가중치가 늘어난다. 각 정점에 사이클을 더할 수 있는 무방향 그래프가 이에 해당한다. (두 정점이 서로를 향하고 있으므로)

 

다익스트라

방향성 비순환 그래프 (DAG : directed acyclic graph)에만 적용된다.

4단계로 이루어진다.

  1. 가장 cost가 적은 정점을 찾는다. (도달하는데 시간이 가장 적게 걸리는 정점)
  2. 이 정점의 이웃 정점들의 cost를 조사한다. (현재의 cost보다 더 저렴한 경로가 존재하는지 확인)
  3. 그래프상의 모든 정점에 대해 반복한다.
  4. 최종 경로를 계산한다.

 

간선의 가중치가 음수인 경우

음의 가중치가 있으면 다익스트라 알고리즘을 사용할 수 없다. 다익스트라 알고리즘에서는 특정 정점을 처리할시에 그 정점에 도달하는 더 저렴한 경로는 없다고 가정해 버리기 때문이다. (음의 가중치 간선이 알고리즘을 망친다.) 음의 가중치를 가진 그래프에서 최단 경로를 찾고 싶은 경우엔 벨만-포드 알고리즘을 사용할 수 있다.

 

구현

//예제

┌───────┐     2     ┌──╌────┐       1
│ start │──────────>│   A   │───────────────┐
└───┬───┘           └───┬───┘               │
    │                   │3                  │
    │       6       ┌──╌v───┐    5      ┌──╌v───┐
    └──────────────>│   B   │──────────>│  end  │
                    └───────┘           └───────┘

3개의 해시 테이블이 필요하다. 그래프, cost, 부모

(특정 정점에 도달하기 위해 거치게 되는 직전 정점을 부모라 한다.)


##그래프 구현
graph = {}
graph["start"] = {}         # 정점 start
graph["start"]["a"] = 6     # 간선들의 가중치 표현
graph["start"]["b"] = 2

graph["a"] = {}             # 정점 a
graph["a"]["end"] = 1

graph["b"] = {}             # 정점 b
graph["b"]["a"] = 3
graph["b"]["end"] = 5

graph["end"] = {}           # 도착점에는 이웃이 없음


## COST 구현
infinity = float("inf")     # 정점의 가격을 저장하는 해시 테이블
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["end"] = infinity

## 부모 구현
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["end"] = None


## 이미 처리한 정점을 추적하기 위한 배열
processed = []

'''
알고리즘 흐름

출발점에서 가장 가까운 정점을 찾는다 
> 이웃 정점의 가격을 갱신한다.
> 만약 이웃 정점의 가격을 갱신하면 부모도 갱신한다.
> 해당 정점을 처리했다는 사실을 기록한다.
> 모든 정점을 처리할 때까지 반복한다.

'''

node = find_lowest_cost_node(costs) # 아직 처리하지 않은 가장 싼 정점을 찾는다.

while node is not None :            # 모든 정점을 처리하면 반복문이 종료된다.
    cost = cost[node]
    neighbors = graph[node]
    for n in neighbors.keys() :     # 모든 이웃에 대해 반복한다.
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost :    # 만약 이 정점을 지나는 것이 가격이 더 싸다면
            costs[n] = new_costs    # 정점의 가격을 갱신
            parents[n] = node       # 부모를 이 정점으로 새로 설정
    processed.append(node)          # 정점 처리 사실 기록
    node = find_lowest_cost_node(costs) # 다음으로 처리할 정점을 찾아 반복

## 가장 싼 정점 찾기
def find_lowest_cost_node(costs) :
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs :             # 모든 정점을 확인
        cost = cost[node]           # 아직 처리하지 않은 정점 중 더 싼 것이 있으면
        if cost < lowest_cost and node not in processed : 
            lowest_cost = cost      # 새로운 최저 정점으로 설정
            lowest_cost_node = node
    return lowest_cost_node

 

 

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘