[Hello Coding 알고리즘] 7. 다익스트라 알고리즘 Dijkstra's algorithm

Bibi·2021년 7월 5일

algorithm algorithm이론

Hello Coding 알고리즘

목록 보기

7/11

Hello Coding 알고리즘

7. 다익스트라 알고리즘 Dijkstra's algorithm

가장 적은 구간을 지나는 경로가 아닌, 가장 빠른 경로를 찾고 싶을 때 사용.

너비 우선 탐색 vs 다익스트라 알고리즘

너비 우선 탐색 : 가중치가 없는 균일 그래프에서 최단 경로를 계산
- 최단 경로 = 가장 적은 수의 구간을 가지는 경로
다익스트라 알고리즘 : 가중 그래프에서 최단 거리를 계산
- 가중치 : 각 간선(구간)에 대한 숫자
- 최단 거리 = 전체 가중치의 합이 가장 작은 경로.

다익스트라 알고리즘

다익스트라 알고리즘의 4단계

가장 가격이 싼 정점 찾기. (=도달하는 데 시간이 가장 적게 걸리는 정점)
그 정점의 이웃 정점들의 가격을 조사함
- 정점의 가격 = 그 정점에 도달하는 데 필요한 것 (시간, 돈.. 등등)
- 만약 현재 가격보다 더 싼 경로가 존재한다면, 가격을 수정함
그래프 상 모든 정점에 대해 1,2를 반복
최종 경로를 계산
- 부모 정점을 찾아가면 완전한 경로를 찾을 수 있다.

용어 설명

가중치 weight

그래프의 각 간선이 가지는 숫자.

가중 그래프 weighted graph

가중치를 가지는 그래프

균일 그래프 unweighted graph

가중치가 없는 그래프

사이클 cycle

그래프가 어떤 정점에서 출발해, 한 바퀴 돌아 같은 정점에서 끝날 때 사이클이 있다고 표현.

사이클을 지나면 최단 경로를 얻을 수 없다.

※ 무방향 그래프 (-로 연결된 정점) 는 두 정점이 서로를 향햐고 있는 것, 즉 사이클을 의미한다.

다익스트라 알고리즘은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)에만, 사이클을 가진 경우에는 가중치가 양수일 떄만 적용 가능.

부모 정점

해당 정점이 직전에 지나온 정점이 부모 정점이 된다.

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

다익스트라 알고리즘에서는 어떤 정점을 이미 처리하고 나면, 그 정점에 도달하는 더 싼 경로는 없다고 가정해 버림.

따라서 음의 가중치를 가진 간선이 있으면 다익스트라 알고리즘을 사용할 수 없다.

(대신, 벨만-포드 알고리즘을 사용하면 음의 가중치가 있어도 최단 경로를 찾을 수 있다.)

다익스트라 알고리즘 구현

3개의 해시 테이블(그래프 해시 테이블, 가격 해시 테이블, 부모 해시 테이블) 그리고 한 개의 배열(처리한 정점 추적)이 필요하다

그래프 해시 테이블

이웃 정점과 그 가격을 함께 저장해야 한다.
정점의 값으로 또 다른 해시테이블을 만들고, 이 해시테이블에 이웃 정점과 가격을 저장한다.

graph= {}

graph["start"] = {} # 시작점의 이웃 정점과 그 가격
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {} ## 정점 a의 이웃 정점과 그 가격
graph["a"]["fin"] = 1

graph["b"] = {} ## 정점 b의 이웃 정점과 그 가격
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {} ## 도착점 (이웃이 없음)

가격 해시 테이블
- 각 정점의 가격(출발점에서 그 정점까지 도달하는 데 걸리는 시간/돈)을 저장한다.
- 가격을 모르는 정점의 가격(예 : 도착점까지의 가격) 은 무한대(∞)로 저장한다.
```
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
```

부모 해시 테이블

각 정점의 부모 정점을 저장한다.

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

정점 추적 배열
- 각 정점은 한 번씩만 처리해야 하므로, 이미 처리한 정점을 추적하기 위한 배열을 추가함
```
processed = []
```

다익스트라 알고리즘 순서

출발점에서 가장 가까운 정점을 찾는다.
이웃 정점의 가격을 갱신한다.
만약 이웃 정점의 가격을 갱신하면, 부모 정점도 갱신한다.
해당 정점을 처리했다는 사실을 기록한다.
모든 정점을 처리할 때까지 1~4를 반복한다.
모든 정점을 다 처리하면 알고리즘이 종료된다.

다익스트라 알고리즘 코드

def find_lowest_cost_node(costs): ## 가장 가격이 싼 정점을 찾는 메서드
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs: ## 가격 테이블의 모든 정점 확인
        cost = costs[node] ## 아직 처리하지 않은 정점 중 더 싼 것이 있으면
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost ## 그 정점을 새로운 최저 정점으로 설정
            lowest_cost_node = node
    return lowest_cost_node
       
node = find_lowest_cost_node(costs) ## 아직 처리하지 않은 가장 싼 정점 찾기
while node is not None: ## 모든 정점 처리 시 반복문 종료
    cost = costs[node] ## 노드의 가격
    neighbors = graph[node] ## 이웃(해시 테이블 객체)
    for n in neighbors.keys(): ## 노드의 이웃 정점들 탐색
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost: ## 만약 이 정점을 지나는 것이 가격이 더 싸다면 (더 빠르다면)
            costs[n] = new_cost ## 해당 정점의 가격 갱신
            parents[n] = node ## 부모 정점 갱신
    processed.append(node) ## 정점을 처리한 것을 기록
    node = find_lowest_cost_node(costs) ## 다음으로 처리할 정점을 찾아 반복