출처:https://www.youtube.com/watch?v=pSqmAO-m7Lk
- 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest path problem)
- 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제(single source shortest path problem)
-
다익스트라 알고리즘이란?
다익스트라 알고리즘은 그래프에서 한 정점에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘이지만 시작노드를 반드시 정해주어야하고 그래프 내에 음의 가중치 합을 가지는 사이클이 없을 때에만 동작하고, 음의 가중치를 갖는 간선이 없을 경우에만 언급하는 시간복잡도에 동작한다.다익스트라는 한 정점으로부터 다른 정점으로의 최단경로와 그 과정에서 거치는 간선들의 가중치 합을 알아낼 수 있다.
-
알고리즘 작동방식
dist 배열에 모든 노드들의 거리를 무한으로 설정해둔다. 그리고 시작 노드 s의 거리는 0으로 놔둔다.우선순위 큐를 이용하며 key-value(노드 index, 거리) 값으로 넣어 어디 노드를 방문해야 할지 저장해둔다.이후 첫번째 노드 (s,0)를 우선순위 큐에 넣고 큐가 빌때까지 다음 노드들을 계속 방문한다
2-1. 만약 경로를 알고 싶다면?
prev 이라는 배열을 만들어 거리가 작아질때마다 인덱스로 넣어주면된다
실제로 풀어보니 이런식으로 푸는 것 보단 한 정점 A에 모이는 다른 정점 B...N 을 배열에 다 넣고dist[A] - edge[B...N][A].cost = dist[B...N]일때 최적의 경로라는 사실을 이용해 구하는것이 더 편했다. 혹은 값이 갱신될때마다 parents라는 배열을 만들어 parents[next] = current 이런 식으로 경로를 저장해 parrents[end]부터 역순으로 해당값을 가져와 확인한다.
2-2. 만약 해당 목적지까지 거리를 알고 싶다면?
