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

다익스트라 알고리즘이란.

그래프의 한 정점(頂點, Vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘(최단 경로 문제, Shortest Path Problem)이다.

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다익스트라 알고리즘

 

다익스트라 알고리즘의 특징은 아래와 같다.

• 장점
  인접 행렬 또는 우선순위 대기열을 사용하여 구현할 수 있으므로 가능한 모든 경로를 확인하는 무차별 접근 방식보다 효율적이다.
  거리뿐만 아니라 경로를 추적하도록 알고리즘을 쉽게 수정할 수 있다.
• 단점
  우선순위 대기열을 사용할 때 간선이 많은 큰 그래프의 경우 느려질 수 있다.
  그래프와 거리를 저장하려면 많은 양의 메모리가 필요하다.
  동일한 거리에 여러 경로가 있는 경우 최상의 경로를 보장하지 않는다.
  지형이나 교통 상황과 같은 다른 요소는 고려하지 않는다.

기본적으로 네비게이션 같은곳에서 많이 사용이 되긴 하는데 지형, 교통상황등 다른 알고리즘들과 합쳐져서 사용이 되곤한다.

 

예시

아래 그림을 보고 1에서 5를 가기 위해서 다양한 경로를 생각해보자.

가장 적은 비용으로 1->5를 가려면 1-4-5 순서로 이동을 하여 50으로 갈수 있다.

모든 경우의 수를 생각해서 가장 적은 비용을 고르면 되는데 얼핏보면 dfs 랑 비슷하다.(참고 포스팅 참고)

 

다익스트라 계산을 단계별로 하나씩 보면

 

• 1에서 갈수있는 정점과 각 가기위해 가중치를 정리한다.
  

  1	2	3	4	5
  0	10	50	30	200

• 방문하지 않은 정점 중 가장 짧은 2가 다음의 기준이 된다.
  2에서 갈수있는 정점을 계산하여 기존과 비교한다.
  2에서는 3만 갈수가 있는데 1->2 = 10 에다가 2->3 = 40 을 더해서 50이랑 3을 가기 위한 기존 값이랑 비교해서 더 작으면 작은 수로 위 표를 변경한다.
  기존 = 50 / 현재 = 50 이니 그대로 둔다.
  

  1	2	3	4	5
  0	10	50	30	200

• 그럼 현재는 3이 기준이고 3에서 갈수 있는 곳을 보니 5가 갈수 있다.
  3에서 갈수있는 정점을 계산하여 기존과 비교한다.
  3에서는 5만 갈수가 있는데 1->2 = 10 에다가 2->3 = 40 을 더해서 50 에다가 3->5 = 10 을 더해서 5을 가기 위한 기존 값이랑 비교해서 더 작으면 작은 수로 위 표를 변경한다.
  기존 = 200 / 현재 = 60 이니 5를 변경한다.
  

  1	2	3	4	5
  0	10	50	30	60

• 다음은 방문하지 않은 4 정점으로 간다.
  4에서 갈수있는 정점을 계산하여 기존과 비교한다.
  4에서는 5만 갈수가 있는데 1->4 = 30 에다가 4->5 = 10 을 더해서 50이랑 5을 가기 위한 기존 값이랑 비교해서 더 작으면 작은 수로 위 표를 변경한다.
  기존 = 60 / 현재 = 50 이니 5를 변경한다.
  

  1	2	3	4	5
  0	10	50	30	50

그럼 최단 경로가 나왔다.

 

이런식으로 진행이 된다.

 

코드 예시는 추후 포스팅에서 작성 후 공유 예정이다.

---

참고 포스팅

https://thenicesj.tistory.com/287

알고리즘 BFS 와 DFS