다익스트라

기록하는 용도·2022년 6월 10일

최단경로 알고리즘 중에 유명한 다익스트라 알고리즘

벨만포드에서는 주어진 s노드에서 제외한 다른 모든 노드의 경로를 구하는데 엣지의 순서대로 차례대로 릴렉스해야한다.

s에서 v로가는 모든 노드까지 최단 경로를 알 수 있다.

그런데 어떤 노드부터 릴렉스 해야하는지 모르니까 n-1 round를 거쳐서 모든 노드에 걸쳐 relax한다.

이러한 방식은, s에서 v뿐만 아니라 다른 모든 노드의 최단 경로를 알 수 있다.

문제는 모든 엣지 만큼 계산되어(노드의 제곱만큼 곱해지게 되어) O(n^3)된다.

다익스트라는 어떤 엣지부터 릴렉스하는게 중복계산을 피하는지 고민해 벨만보다 빠른 알고리즘을 설계할 수 있다.

a노드 0 나머지는 무한대로 초기화 시키고, 제일 작은 값 선택해서(a) 인접한 모든 노드를 릴렉스한다. (b의디스턴스5 c의디스턴스1이된다.)

작은 문제가 큰 문제 속에 비슷한 형태로 포함되어있는 다이나믹 프로그래밍 유형이라고 할 수 있다.

다익스트라라는 것은 현재까지 알고있던 최단 경로를 계속해서 갱신한다.

특정 행에서 특정한 열로가는 비용을 테이블로 작성한다.
1을 선택한다면 연결되어있는 노드의 비용으로 갱신한다.
현재 연결 안되어있어서 무한이라고 적어준다.
이 상태에서 가장 비용이 적은 노드를 선택한다.

그래서 그 다음으로 선택된 노드가 연결된 노드를 확인할때,
현재 1비용을 받고, 3을 더해서 4라는 비용을 갈 수 있다는 것을 확인하고,
새롭게 갱신한다.

특정한 노드를 거쳐서 가는경우 그 더 싼 비용으로 갱신한다.
→ 다익스트라 알고리즘의 기본 원리

그 다음으로 비용이 저렴한 노드를 설정하고, 기존의 갈수 없다고 생각했던(무한으로 뒀던) 비용을 따져서 갱신이 이루어지는것을 확인할 수 있다.

결과적으로 갱신된 테이블(1에서 출발해 각각 노드로 출발해) 최소 비용이라고 할 수 있다.

특정한 정점에서 출발해서 다른 모든 정점으로 가는 비용을 구하는 다익스트라 알고리즘을 구할 수 있다.

선형탐색으로 구하면 정점의 개수는 많은데 간선은 적을때 치명적일 수 있다.

힙을 통해서 큰값 작은값이 최상단 노드에존재한다는 특징을 이용해 가장작은 값을 가져오는 과정이 logn이라 전체코드를nlogn으로 만들 수 있다.

최단경로와 다익스트라 알고리즘

단일 정점에서 모든 다른 정점으로의 최단 경로 구하기
- 다익스트라 알고리즘: 대표적인 탐욕법
- 그래프 내 간선의 가중치가 음수인 것이 하나라도 있다면 사용불가

A에서 어떤 경로로 가는 최단경로를 확인할 수 있다.
예제)A에서 F로 가는 최단 경로는?
백트레이싱을 통해서 확인할 수 있다.
스택을 통해 확인하면,

얘를 팝하게되면
A→ C→E→F
이게바로 A에서 F로 가는 최단 경로이다.

초기에는 최단경로를 구하지않은 상태이므로 무한대로 값을 표시한다.

1번 정점과 인접한 노드들은 2,4,5 이므로 무한대에서 값을 변경해준다

다음으로 최단 거리 노드인 5 노드를 보면 1과 4가 연결되어있는데 1은 이미 방문했으므로 4번 노드를 살펴보아 1+2를 더해 3으로 바뀐다.

다음으로 이미 방문한 1번노드, 5번노드를 제외하고 가장 짧은노드 4번노드(3)을 살펴보면, 4번노드는 3번,1번,5번과 연결되어있다.
살펴보지않은 3번노드를 9로 갱신시킬 수 있다.

최단 경로의 길이:1-5-4