티스토리 뷰
서론
다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 컴퓨터 과학자 에츠허르 다익스트라가 1956년에 고안했으며 삼년 뒤에 발표했습니다. 최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS-IS(Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First)에서 주로 사용됩니다.
그래프에서 정점까지 최단 경로를 구하는 문제는 여러가지 방법이 있습니다.
- 하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제
- 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
- 하나의 목적지로 가는 모든 최단 경로를 구하는 문제
- 모든 최단경로를 구하는 문제
다익스트라 알고리즘은 여기서 두번째 방법으로, 하나의 정점에서 다른 모든 정점들의 최단 경로를 구합니다.
간선들은 모두 양의 간선을 가집니다.
다익스트라 알고리즘
시작할 꼭지점은 초기점으로, 꼭지점 Y의 거리를 초기점에서 Y까지의 거리로 정의합니다. 다익스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 간선 완화(edge relaxation)이라고 합니다.
- 모든 꼭짓점을 미방문 상태로 표시합니다. 미방문 집합이라는 모든 미방문 꼭지점의 집합을 만듭니다.
- 모든 꼭짓점에 시험적 거리 값을 부여합니다. 초기점을 0으로, 다른 모든 꼭지점을 무한대로 설정합니다. 또한, 초기점을 현재 위치로 설정합니다.
- 현재 꼭지점에서 미방문 인접 꼭지점을 찾아 그 시험적 거리를 현재 꼭지점에서 계산합니다. 새로 계산한 시험적 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣습니다. 예를 들어, 현재 꼭짓점 A의 거리가 6이라고 표시되었고, 인접 꼭짓점 B로 연결되는 변의 길이가 2라고 한다면, A를 통한 B까지의 거리는 6 + 2 = 8이 됩니다. 이전의 B까지의 거리가 8보다 컸다면 8로 바꾸고, 그렇지 않다면 그대로 놔둡니다.
- 만약 현재 꼭짓점에 인접한 모든 미방문 꼭짓점까지의 거리를 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 미방문 집합에서 제거합니다. 방문한 꼭짓점은이후에는 다시 방문하지 않습니다.
- 두 꼭지점 사이의 경로를 찾는 경우 : 도착점이 방문한 상태로 표시되면 멈추고 알고리즘을 종료합니다.
- 완전 순회경로를 찾는 경우 : 미방문 집합에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면 이는 출발점과 미방문 집합 사이에 연결이 없는 경우이므로 멈추고 알고리즘을 종료합니다.
- 아니면 시험적 거리가 가장 작은 다음 미방문 꼭짓점을 새로운 "현재 위치"로 선택하고 3단계로 되돌아갑니다
위의 코드는 우선 순위 큐를 이용한 다익스트라 알고리즘으로, 최적 경로를 저장하며, 지정된 노드에 도달할 경우 종료 되어집니다.
코드
출처 : https://hsp1116.tistory.com/42,
반응형