최단경로 다익스트라

다익스트라

자료구조

그래프

큐

 

특징

최단거리를 구하는 알고리즘

한지점에서 다른 정점까지의 각각의 최단거리를 구 할 수 있다. ( 모든 정점간의 최단거리 - 플로이드 )

음의 가중치를 같는 간선이 나올경우 구할 수 없다(음이 나와도 구할 수 있는 경우 - 벨만포드)

 

관련 알고리즘

최단 거리 알고리즘

1. 다익스트라
2. 플로이드
3. 벨만포드

 

개념

그래프에서 시작정점을 정한다.

시작 정점으로부터 다른 정점으로의 최단거리를 계속 업데이트 한다. dist[i]

현재 지점까지의 최소 거리 dist[i]와 현재 정점 i와 연결된 정점 v의 가중치를 더한 값이 dist[v]보다 작을 경우 dist[v]를 업데이트 하고 우선순위 큐에 넣는다.

우선순위 큐의 값이 없어 질때까지, 계속한다.

 

dist[] 배열은 최대 값으로 초기화 한다.

출발점 S의 최대값은 0 이기 때문에 dist[s]를 0으로 초기화한다.

출바점 s에서 연결된 두개의 점 a,c에 관하여 dist[s]+e(s,a)와 dist[a]를 비교하여 앞의 식이 더 작은 값이라면, 새로운 최소값이 나온것이기 때문에 dist[a]를 업데이트하고 해당 노드를 우선순위 큐에 집어 넣는다.

S 정점의 연결된 간선을 모두 확인하고나서 q에서 제일 가중치가 낮은 값을 가진 노드를 꺼내와 똑같은 일을 반복한다. 위으그래프에선 a가 꺼내 질 것이다.

위와 같은 문제에서 여러 노드들을 돌아다니다보면, 같은 노드가 여러번 들어갈 수 있다. 예를 들어 s-c-b의 노드가 선택되어 b-a가는 간선이 큐에 먼저 들어 갈 수 있다. 하지만, 다시한번 최소값을 비교할때, 값이 업데이트 되지 않기 때문에 상관없다.

이런한 불필요한 작업을 없애기 위해 큐에 넣기전에 확인하는 방법등이 있지만 구현하기 어렵다고 한다.

혹은 큐에서 꺼내어 다음 노드를 선택하는 방식 대신에, dist[] 배열을 탐색하여 가장 작은 값의 노드를 선택 할 수 있다.

 

추천문제

BOJ 1753 최단경로

다익스트라로 해결할 수 있는 가장 기본적인 개념문제이다.