[c++] 다익스트라 알고리즘 | 최단 경로

[가중치 그래프 (Weighted Graph)]

• 네트워크(network)라고도 한다.
• 간선에 가중치가 할당된 그래프이다.
  • 비용 (cost)
  • 가중치 (weight)
  • 길이 (length)

 

가중치 표현 방법

• 인접 행렬 M[i][j]를 가중치를 위해 사용한다.
• 추가적인 메모리 사용 없이 가중치를 표현할 수 있다.
• 인접행렬 M을 이용한 그래프 표현에서 M[i][j]가 간선 (i, j)의 가중치 값을 나타낸다.
• 만약 간선 (i, j)가 존재하지 않으면 M[i][j]가 매우 큰 값을 갖도록 한다.

 

[최단 경로]

• 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로이다.
• 간성의 가중치는 비용, 거리, 시간 등이 있다.

 

A에서 부터 모든 정점까지의 최단 경로를 구할 수 있는 방법은?

 

=>  다익스트라 알고리즘!

 

 

 

 

 

 

[다익스트라(Dijkstra) 알고리즘]

• 시작 정점 v에서 모든 다른 정점까지의 최단 경로를 찾는 대표적인 최단 경로 탐색 알고리즘이다.
• 모든 간선이 양인 값을 가질 때(음수가 없을 때) 사용 가능하다.
• 인공위성 GPS 소프트웨어, 내비게이션 등에 가장 많이 사용된다.
• 매 상황에서 가장 비용이 적은 노드를 선택한다.

 

 

탐욕 (greedy) 알고리즘

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해

나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만,

그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그 것이 최적이라는 보장은 없다.

=> 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

 

다익스트라 알고리즘은 탐욕 알고리즘을 내포하고 있다.

 

 

다익스트라 알고리즘

• distance(거리)값 갱신
  • 새로운 정점이 S에 추가되면 distance값을 갱신한다.

 

 

다익스트라 알고리즘 예시 문제

그럼 이제 다익스트라 알고리즘이 어떻게 작동하는 것인지 설명드리겠습니다.

 

밑 사진에서 시작 정점 A에서 부터 모든 다른 정점까지의 최단 경로를 찾는 과정을 예시로 들겠습니다.

정점 A부터 D까지 차례대로 가중치를 계산해봅시다.

이해하기 쉽도록 가중치를 가는데 드는 돈으로 설명드리도록 하겠습니다.

 

- 1번째

정점 A는 시작 정점이기 때문에 최단경로가 0으로 발견된 정점입니다. 따라서 집합 S에 들어갑니다.

정점 A에서 출발했을 때 정점 B까지는 2원을 내고 도착할 수 있습니다.

정점 A에서 출발했을 때 정점 C까지는 7원을 내고 도착할 수 있습니다.

정점 A에서 출발했을 때 정점 D까지는 9원을 내고 도착할 수 있습니다.

 

이중에서 가는데 가장 적은 비용이 드는 정점은 B이므로 최단 경로가 발견되었기 때문에 정점 집합 S에 B가 들어가게됩니다. 이것이 왜 최단경로를 보장할 수 있는지는 밑에서 다루겠습니다.

 

그렇게 최단경로가 발견되지 않은 정점들의 거리를 정점 집합 S에 있는 정점들을 통해 계속해서 가장 작은 비용을 들여 갈 수 있는 경로를 찾습니다.

여기서 헷갈리면 안되는 점은 정점 집합 S에 들어있는 정점들을 집합에 들어간 순서대로 방문하지 않아도 된다는 것 입니다. 방문하려는 정점이 정점 집합 S에 들어있기만 한다면 어떤 정점을 방문해서 타겟 정점으로 가는지는 상관이 없습니다

그저 가장 낮은 비용이 드는 경로를 찾으면 될 뿐입니다.

 

- 2번째

정점 C는 원래 A -> C경로를 통해서만 갈 수 있었기 때문에 7원을 들여 가야했지만 정점 집합 S에 정점 B가 들어왔기 때문에 이제 B를 통해서 또한 C를 방문할 수 있습니다. 따라서 C는 A -> B -> C의 경로를 통해 간다면 더 작은 비용인 5원이 듭니다.

하지만 정점 D는 B를 거쳐 갈 수 없기 때문에 똑같이 A -> D의 경로를 이용해 9원의 비용이 듭니다.

 

이렇게 가장 적은 비용이 드는 정점 C는 최단 경로가 발견되었습니다. 따라서 정점 집합 S에 C가 들어가게됩니다.

 

- 3번째

마지막으로 정점 D는 A -> B -> C -> D의 경로를 이용한다면 6원의 비용이 듭니다. 이렇게 D의 최단 경로가 발견되었고 D가 정점 집합 S에 들어가면서 다익스트라 알고리즘이 종료됩니다.

 

이 경우에는 3번만에 모든 정점의 최단 거리가 발견되었습니다. 이해되셨나요?.

 

 

• 다익스트라 알고리즘 : 최단 경로 증명

 

• distance값이 가장 작은 정점이 u이다.
• v에서 u까지의 최단경로는 1번 경로이다.

 

• 경로 2번은 1번보다 항상 길 수 밖에 없다. (3번은 양수이기 때문에)

 

• 따라서 매 단계에서 distance값이 가장 적은 정점들을 추가하면 모든 정점까지의 최단 거리를 구할 수 있다.

 

 

• 다익스트라 알고리즘 : 시간 복잡도
  • 네트워크에 N개의 정점이 있다면
    • 주 반복문을 N번 반복
    • 내부 반복문을 2N번 반복
  • => 다익스트라의 최단 경로 알고리즘은 O(n의 2승)의 시간 복잡도이다.

 

 

[최단 경로 탐색 알고리즘]

• 단일 출발점 최단 경로 : 다익스트라 알고리즘, 벨만 포드 알고리즘
• 모든 출발점 최단 경로 : 플로이드 알고리즘
• 다익스트라는 가중치가 양수일 때만 실행할 수 있고, 가중치가 음수일 때는 벨만 포드 알고리즘을 사용하면 된다.

 

---

 

이렇게 다익스트라 알고리즘에 대해 알아보았습니다.