[알고리즘/최단경로] 다익스트라 (Dijkstra) 알고리즘

다익스트라 알고리즘이란

• 특정한 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 문제의 방법
• 음의 간선이 있을 경우 사용할 수 없음

 

다익스트라 원리

• 특정한 하나의 정점을 잡고, 그 정점과 이웃한 정점들의 비용을 각각 확인
• 그 중 가장 적은 비용이 드는 정점 기준으로 다시 한번 확인 (Why ? 직접 이웃한 정점으로 가는 것보다 이웃한 정점을 거쳐서 가는 것이 더 적은 비용이 들수도 있기 때문)
• 과정
  • 출발 노드 설정
  • 출발 노드 기준, 각 노드의 최소 비용 저장
  • 방문하지 않은 노드 중에서 가장 비용이 적게 드는 노드 선택
  • 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소비용 갱신

 

다익스트라 알고리즘 기본로직

• 시작점의 최단거리를 0, 나머지 정점의 최단거리는 INF (무한대. 즉, 가질 수 없는 가장 최대 값) 으로 초기화
• 시작점에 연결되어 있는 정점들부터 탐색해서 현재 정점 최단거리가 (시작점 최단거리 + 시작점과 현재 정점 사이의 최단거리)보다 크다면 현재 정점 최단거리 = (시작점 최단거리 + 시작점과 현재 정점 사이의 최단거리) 로 갱신

 

우선순위 큐(힙구조) 이용

• 보통 일차원 배열을 매번 탐색해서 가장 짧은 거리를 찾아내지만,
• 힙 구조를 이용하면 더욱 빠른 시간 내에 구현 가능
• 최소 힙 사용시, 가장 작은 최단 경로를 가진 정점 빠르게 구할 수 있음
• 구현 방법
  • 모든 정점들을 우선순위 큐에 넣음 (정점 인덱스, 최단거리, 이전 정점 / 최단거리 기준으로 구성)
  • 가장 위에 있는 값을 꺼내서, 기존에 있던 배열과 최단거리 비교
  • 배열에 있는 값이 더 작으면 연산 X, 같거나 크면 연산
  • 인접 정점 계산 ( dist[2] = min(dist[2], dist[5] + adj[5][2] ) -> 2번 노드가 인접 정점, 5가 현재 정점

 

시간 복잡도

• 이차원 배열(인접 행렬) 이용 시 O(n^2) 
  • 정점의 개수가 많은데 간선은 적을때 비효율적
• heap 이용 시 O(N * logN)
  • 인접리스트 방식 활용

 

 

 

 

---

 

참고하면 좋을 블로그:

m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234424646&proxyReferer=https:%2F%2Fwww.google.com%2F

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

 

글 작성 시 참고:

hsp1116.tistory.com/42

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

velog.io/@max9106/Algorithm-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra-Algorithm

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