☞ 최단 경로를 구하기 위해선 어떤 방법을 써야할까?
우리는 BFS(너비우선탐색)을 이용해서 어떤 한 점까지 최소 거리를 알 수 있었고, 또한 경로를 구할 수 있었다.
하지만 너비우선탐색을 이용해 구할 때는 가중치가 없을 때라는 조건이 있었다.......
가중치가 있고, 방향성 그래프일때 어떤 방식을 이용해 최단 경로, 최소 거리를 구할 수 있을까?...
여기서 다익스트라 알고리즘이 나온다. 다익스트라 알고리즘이란 그래프 간선에 가중치가 있을 때 최단 경로를 구할 수 있는 알고리즘이며, 너비 우선탐색을 조금 변형해서 만든 알고리즘이라 할 수 있다.
BFS는 큐를 사용해 최단 경로를 구하는 반면, 다익스트라 알고리즘은 우선순위큐를 사용해 최단 경로를 구할 수 있다.
다익스트라의 원리를 살펴보면,,,,,
먼저 dist는 시작점(0의 값을 갖는다)부터 다른 점까지의 거리를 저장하며, 우선순위큐는 pair<거리, 정점>을 저장시켜준다.
priority_queue<pair<int, int>> pq;
bfs처럼과 비슷하게 알고리즘을 작성하지만, 여기서 크게 다른 점은 한 점의 원래의 dist값보다 우선순위큐를 이용해 구한 새로운 nextDist값이 더 작을 때 바꿔줌을 알 수 있다.
vector<int> dijkstra(int start) {
vector<int> dist(V+1, INF);
dist[start] = 0;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, start));
while (!pq.empty()) {
int cost = -pq.top().first;
int here = pq.top().second;
pq.pop();
if (dist[here] < cost) continue;
for (int i = 0; i < adj[here].size(); i++) {
int there = adj[here][i].first;
int nextDist = cost + adj[here][i].second;
//원래의 dist값과 큐를 이용해 구해진 nextDist값을 비교해 nextDist값이 더 적으면 대체.
if (dist[there] > nextDist) {
dist[there] = nextDist;
pq.push(make_pair(-nextDist, there));
}
}
}
return dist;
}※ 자! 근데, 방향성 그래프일때 사용 할 수 있다했는데, 무방향성 그래프일때는 어떻게 최단 경로를 구할 수 있을까?
- 무방향성 그래프는 쉽게 말해 방향이 없고 둘 다 갈 수 있기 때문에, 방향을 가진 간선 2개를 이용해 무방향성에서 방향성으로 바꿔준다. (- => ↔) (단, 간선의 가중치가 음수가 있을 때는 음수 사이클이 발생 할 수 있기 때문에 불가능하다.)
궁금하신 것이 있으시다면 댓글로 남겨주세요!~
