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

Dijkstra

다익스트라 알고리즘은 시작점으로 부터 나머지 정점까지 최단거리를 구할 때 사용된다.

간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘이다.

단, 가중치는 음수(-) 값을 가지지 않는다.

 

구현방법

다익스트라 알고리즘은 각각의 정점에 대해서 정점 s에서 정점 v까지의 최단 거리를 d[v]에 저장하면서 탐색한다.

알고리즘 시작 시, d[s] = 0이고, s가 아닌 다른 모든 정점에 대해서는 d[v] = 해당가중치 로 시작한다.

알고리즘이 종료 시, d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 된다.

다익스트라 알고리즘은 다음과 같다.

Graph[A][B]는 A에서 B까지 가는 데 드는 비용 이라고 하자.

 

1. 주어진 N개의 정점 그래프에서 NxN 2차원 배열을 만들고, 그 안에 각 정점 사이의 가중치를 저장한다.

2. 본인 노드에는 0, 다른 노드들에는 Infinity(무한대)로 초기화한다.

 

3. 출발점으로부터의 최단거리를 저장할 배열 distance[v]를 만들고, 출발 노드에는 0으로, 출발점을 제외한 다른 노드들에는 Infinity(무한대)로 선언한다.

 

4. 방문 완료된 노드를 저장할 visited[i]를 만들고, 방문 완료된 노드는 true로 만든다.

 

5. "미방문" 상태인 모든 노드들 중, 출발 노드로부터의 거리가 제일  짧은 노드 하나를 골라서 그 노드를 curr에 저장한다.

• 모든 노드를 순회해 거리가 제일 짧은 노드를 찾아야한다. (우선순위큐를 활용하면 이 비용을 줄일 수 있다.)

6. 출발 노드부터 curr까지 distance[curr]+Graph[curr][B] 를 distance[B]와 비교하여, 더 작을 경우 출발 노드에서 B노드 까지 최소 비용인 distance[B]를 distance[curr]+Graph[curr][B]로 갱신한다.

 

7. curr의 모든 이웃 노드에 대해 노드 개수만큼 계속 수행한다.

 

8. curr노드의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 curr은 사용하지 않는다.

 

9. 이렇게 distance[] 배열이 모두 방문 완료 상태가 될 때까지 반복한다.

 

10. 최종, distance[] 배열이 출발 노드로부터 모든 각 노드까지의 최소 비용이 된다.

 

 

실제 예시

위와 같이 그래프가 준비되어있다.

컴퓨터에서는 해당 그래프를 2차원 배열로 처리해야한다.

0	2	5	1	Infinity	Infinity
2	0	3	2	Infinity	Infinity
5	3	0	3	1	5
1	2	3	0	1	Infinity
Infinity	Infinity	1	1	0	2
Infinity	Infinity	5	Infinity	2	0

직접 연결돼 있는 정점은 해당 가중치로, 거쳐가야하는 경우는 Infinity로 초기화 한다.

이 상태에서 1번 노드를 선택한다.

1번 노드에서 각 노드로 가는 최소 비용 distance[]은 다음이 된다. 이 배열을 갱신하여 1번 노드로 부터 각 노드별로 최소 비용을 알아낸다.

0

2

5

1

Infinity

Infinity

distance[0]은 방문완료된 노드가 된다.

방문 완료된 노드를 제외하고 가장 작은 비용을 가지는 4번 노드를 선택한다.

4번노드를 거쳐서 가는 노드들의 비용을 확인하여 최소 비용 배열( distance[] )을 갱신하면 된다.

0

2

5

1

2

Infinity

1->4->3를 거쳐갈 때 최소 비용이 1+3<5 이므로 4로 갱신한다.

1->4->5를 거쳐 갈때 최소 비용이 2<Infinity 이므로 2로 갱신한다.

2번의 경우 4를 거쳐가는 것보다 다이렉트로 가는 것이 더 비용이 적기 때문에 갱신하지 않는다.

이제 다음 방문하지 않은 노드들 중에서 비용이 가장 작은 2번 노드가 선택된다.

0

2

4

1

2

Infinity

2번을 거쳐 4번 노드로 갈 경우 비용은 4로 1보다 크므로 갱신되지 않고,
3번 노드는 2번을 거쳐가면 2+3로 4보다 크므로 갱신 변화가 없다.

이제 다음 방문하지 않은 노드들 중에서 비용이 가장 작은 5번 노드가 선택된다.

0

2

4

1

2

Infinity

5번을 거쳐 3번으로 갈 경우, (5번까지 비용 2 + 5번에서 3번까지 비용 1)= 3 < 4 이고,

5번을 거쳐 6번으로 갈 경우, (5번까지 비용 2 + 5번에서 6번까지 비용 2)=4 < Infinity 이므로

다음과 같이 갱신된다.

0

2

3

1

2

4

이제 다음 방문하지 않은 노드들 중에서 비용이 가장 작은 3번 노드가 선택된다.

0

2

3

1

2

4

최소 비용은 갱신되지 않는다.

마지막으로, 6번 노드가 선택된다.

여기서도 갱신되지 않고, 최종 결과는 다음과 같이 된다.

0

2

3

1

2

4

 

다음 블로그를 참고하여 공부했다.

https://m.blog.naver.com/ndb796/221234424646

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

프로그래머스 <배달> 문제 푸려고 다익스트라 알고리즘 공부했는데, 슬슬 그래프 문제도 풀 때인 거 같아서

플로이드 와샬, 벨만 포드  도 다시 공부해야겠다...

다 까먹었다 .. ! 그래프 넘 어려운 것..

 

우선순위 큐 참고하기. 비효율적인 다익스트라 말고.

https://velog.io/@lre12/%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

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

https://www.apexcel.blog/algorithm/graph/shortest-path/dijkstra/

최단 경로(Shortest Path) 1 - 다익스트라 알고리즘(Dijkstra's Algorithm)