다익스트라 알고리즘

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

• 최단 시간 경로

  • 너비 우선 탐색이 최단 경로(가장 짧은 단계)였던 반면, 다익스트라 알고리즘은 가장 빠른 경로 즉, 최단 시간 경로를 탐색한다. 다음과 같은 단계를 거친다.

    1. 가장 가격이 "싼" 정점을 찾는다. 가장 가격이 싼 정점이란 도달하는 데에 걸리는 시간이 가장 짧은 정점을 말한다.
    2. 이 정점의 이웃 정점들의 가격을 조사한다.
    3. 그래프 상의 모든 정점에 대해 이 일을 반복한다.
    4. 최종 경로를 계산한다.

• 예시

  

  최단 경로를 찾자!

  • 위 그래프에서 A까지 가는 시간은 6, B까지 가는 시간은 2이므로 B가 가장 싼 정점이다.

  • 이 때 도착점까지 얼마 걸리는 지는 알 수 없으므로 무한대라고 한다.

  • 정점 B의 이웃 정점의 가격을 조사한다. B에서 A를 가는 시간은 3이므로 출발점에서 B를 경유하여 A로 가는 시간은 5이다. 즉 A까지 가는 시간은 6에서 5로 줄어든다.

    또한 B에서 도착점까지는 5이므로 도착점까지 걸리는 시간이 무한대에서 7로 바뀐다.

  • 정점 A의 주변 가격을 조사한다. A에서 도착점까지 1이 걸리므로 A를 경유하여 출발점에서 도착점까지 걸리는 시간은 6이 된다. 즉 도착점까지 걸리는 최단시간이 7에서 6으로 줄어든다.

• 가중치, 사이클
  • 그래프의 간선이 가지는 숫자를 가중치라고 한다. 가중치를 가지는 그래프를 가중 그래프(weighted graph)라고 한다. 반대로 가중치가 없는 그래프는 균일 그래프이다. 균일그래프에서 최단 경로 계산 시에는 너비 우선 탐색을 사용하고 가중그래프에서는 다익스트라 알고리즘을 사용한다.
  • 사이클(cycle)이란 어떤 정점에서 출발해서 한 바퀴 돌아 _같은 정점_에서 끝난다는 뜻이다. 무방향 그래프는 사실 사이클을 의미한다.
  • 다익스트라 알고리즘은 방향성 비순환 그래프 또는 사이클을 가진 경우에는 가중치가 양수일 때만 적용된다. (Hello Coding p173 참조) 음의 가중치를 가진 그래프에서 최단 경로를 찾으려면 벨만-포드 알고리즘을 사용하면 된다.

• 알고리즘

  

  node = find_lowest_cost_node(costs)
  while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  for n in neighnors.keys():
    new_cost = cost + neighbors[n]
    if cost[n] > new_cost:
      cost[n] = new_cost
      parents[n] = node
    processed.append(node)
  node = find_lowest_cost_node(costs)