다익스트라 알고리즘

08 Mar 2018 • Algorithm

Chapter 7 다익스트라 알고리즘 (Dijkstra algorithm)

  • 그래프의 간선에 가중치를 준 가중 그래프를 공부.
  • 가중 그래프에서 X 까지의 최단 경로를 구하는 다익스트라 알고리즘을 배움.
  • 그래프에 사이클이 있는 경우에는 다익스트라 알고리즘을 쓸 수 없다는 것을 배움.

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

  • 너비 우선 탐색은 가장 빠른 길이 아니라 가장 짧은 길, 즉 최단 경로를 구하는 알고리즘
  • 다익스트라 알고리즘은 가장 빠른 경로, 최단 시간 경로를 구하는 알고 리즘

2. 다익스트라 알고리즘

다익 스트라 알고리즘은 4단계로 이루어짐

  1. 가장 “가격”이 “싼” 정점을 찾음. 가장 가격이 싼 정점이란 도달하는데 걸리는 시간이 가장 적게 걸리는 정점을 말함(간선의 가중치가 작은것)
  2. 이 정점의 이웃 정점들의 가격을 조사.
  3. 그래프 상의 모든 정점에 대해 [1:2]를 반복
  4. 최종 경로를 계산.

3. 용어 설명

  • 다익스트라 알고리즘을 사용할 때 그래프의 각 간선은 어떤 숫자를 가지는데 이숫자를 가중치 라고함.
  • 가중치를 가지는 그래프는 가중 그래프 라고 함.
  • 가중치가 없는 그래프는 균일 그래프 라고 함.
  • 균일 그래프에서 “최단 경로”를 계산할 때는 너비 우선 탐색을 사용.
  • 가중 그래프에서 “최단 경로”를 계산할 때는 다익스트라 알고리즘을 사용.
  • 그래프는 사이클 이라는 것을 가질 수도 있다. (어떤 정점에서 출발하여 다시 자신에게 돌아오는 경로가 있는 것)
  • 6장에서 본 방향 그래프와 무방향 그래프에서 무방향 그래프는 사이클 이다.
  • 무방향 그래프에서는 각 정점에 사이클을 더 할수 있다.
  • 다익스트라 알고리즘은 방향성 비순환 그래프 또는 사이클을 가진 경우에는 가중치가 양수 일때만 적용

방향성 비순환 그래프 (dag)는 사이클이 없는 그래프를 말한다.

4. 다익스트라 알고리즘을 사용한 물물 교환

  • 다익스트라 알고리즘의 핵심은 가장 가격이 싼 정점을 찾는 것.
  • 정점을 찾는 과정중 경로를 확인 할려면 해당 정점의 부모정점도 가지고 있어야 한다.

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

  • 음의 가중치가 있으면 다익스트라 알고리즘을 사용할 수 없다.
  • 만약 음의 가중치를 가진 그래프에서 최단 경로를 찾고 싶으면 벨만-포드 알고리즘을 사용하면 된다.

6. 구현

  • 3개의 해시테이블의 필요( 그래프, 가격, 부모 )
  • 이웃 정점과 함께 그 이웃의 가격도 저장 해야 한다.
  • 각 정점의 가격을 저장하는 해시 테이블이 있어야 한다.
  • 부모를 나타내는 추가적인 해시 테이블도 필요 함.
  • 각 정점은 한 번씩만 처리해야 하므로 이미 처리한 정점을 추적하기 위한 배열도 있어야 한다. 
    while 모든 정점을 처리할 때까지
  출발점에서 가장 가까운 정점을 찾는다
  이웃 정점의 가격을 갱신한다.
  만약 이웃 정점의 가격을 갱싱하면 부모도 갱싱한다.
  해당 정점을 처리 했다는 사실을 기록한다.

graph = {
    'start': {
        'a': 6,
        'b': 2,
    },
    'a': {
        'fin': 1
    },
    'b': {
        'a': 3,
        'fin': 5,
    },
    'fin': {

    }
}

costs = {
    'a': 6,
    'b': 2,
    'fin': float('inf'),
}

parents = {
    'a': 'start',
    'b': 'start',
    'fin': None
}

processed = list()


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)  # 다음으로 처리할 정점을 찾아 반복


result = list()


def find_path(key):
    if parents[key] == 'start':
        result.append('start')
        return
    else:
        find_path(parents[key])
        result.append(parents[key])


find_path('fin')
print('최단 시간 경로: ', ' -> '.join(result))
print('총 가격:', costs['fin'])

벨만-포드 알고리즘

  • 그래프 상에 존재하는 두 노드 간의 최단 거리를 구하고 싶을 때 이용할 수 있다.
  • 다익스트라에서 할 수 없었던 음의 가중치도 계산 할수 있다.
  • 하지만 다익스트라보다 시간 복잡도가 높다.
  • 계속해서 모든 간선을 이용하여 A정점에서 B정점으로 갈 때, 거리가 짧아지는 경우가 생긴다면 계속 업데이트를 해주는 방식이다.
  • 업데이트 되지 않아도 반복은 계속 된다.
  • V(정점)*E(간선)번 반복후 종료 된다.

  • 최단 경로에 도달할 수 있는지 판단 할 수 있다.

  • 조건

    최단 경로는 사이클이 포함 될수 없기 때문에, 최대 |V|-1개의 간선만 사용 할 수 있다. 최단 거리가 업데이트 되는 노드가 없어 질때까지 계속해서 반복하여 구해주고, 음의 가중치로 인해 업데이틀 무한히 하게 되는 경우 탈출 시켜 주어야 한다.(무한히 반복할 때는 최단 거리가 없다고 한다)

  1. 시작점은 0으로 나머지 정점은 무한대로 초기화

  2. 모든 정점의 개수만큼 반복 하면서 모든 간선에 대해 최단 거리를 구한다.

  3. 모든 간선을 돌면서 음의 가중치를 갖는 사이클이 존재 하는지 판단.

 Algorithm

Comments

Other Posts