다익스트라 알고리즘(Dijstkra Algorithm)이란, 그래프가 주어졌을 때 특정 노드 두 개 사이의 최단 거리를 찾을 수 있는 알고리즘이다.
1부: 다익스트라 알고리즘을 이용해 최단 경로 복원하기
간단히 구현해보자면 다음과 같다:
코드 A
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#define NMAX 1500
using namespace std;
typedef pair<int, int> pii;
int main()
{
int v,e;
cin>>v>>e;
int k;
cin>>k;
vector<pii> rd[NMAX]; // road
for(int i=0;i<e;i++)
{
int u,v,w;
cin>>u>>v>>w;
rd[u].push_back(pii(v,w));
}
int dis[NMAX];
for(int i=1;i<=v;i++)
{
dis[i]=INT_MAX;
}
dis[k]=0;
priority_queue<pii> pq;
pq.push(pii(-0,k));
while(!pq.empty())
{
pii x=pq.top();
pq.pop();
int cn=x.second; // current node
int cd=-x.first; // current distance
if(cd>dis[cn])
{
continue;
}
for(auto j:rd[cn])
{
int nn=j.first; // next node
int nd=cd+j.second; // next distance
if(nd<dis[nn])
{
dis[nn]=nd;
pq.push(pii(-nd,nn));
}
}
}
for(int i=1;i<=v;i++)
{
if(dis[i]==INT_MAX)
{
cout<<"INF\n";
}
else
{
cout<<dis[i]<<"\n";
}
}
return 0;
}
참고로 이 코드는 백준 1753번: 최단경로 문제의 해답 코드이다. https://www.acmicpc.net/problem/1753
이 코드는 시작 노드(k)에서 나머지 노드들로 가는 최단 경로의 길이를 찾아준다.
다익스트라 알고리즘은 즉, 그 길이를 찾아주는 알고리즘이다.
따라서 그 경로 자체는 알 수 없다.
하지만 알 수 있는 방법이 있다.
코드를 조금 수정해보았다.
코드 B
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#define NMAX 1500
using namespace std;
typedef pair<int, int> pii;
int main()
{
int v,e;
cin>>v>>e;
int k;
cin>>k;
vector<pii> rd[NMAX]; // road
int bef[NMAX]; // bef 배열: 특정 노드를 최단 경로를 따라 이동했을 때 그 노드 직전에 방문한 노드
for(int i=0;i<e;i++)
{
int u,v,w;
cin>>u>>v>>w;
rd[u].push_back(pii(v,w));
}
int dis[NMAX];
for(int i=1;i<=v;i++)
{
dis[i]=INT_MAX;
}
dis[k]=0;
priority_queue<pii> pq;
pq.push(pii(-0,k));
while(!pq.empty())
{
pii x=pq.top();
pq.pop();
int cn=x.second; // current node
int cd=-x.first; // current distance
if(cd>dis[cn])
{
continue;
}
for(auto j:rd[cn])
{
int nn=j.first; // next node
int nd=cd+j.second; // next distance
if(nd<dis[nn])
{
dis[nn]=nd;
pq.push(pii(-nd,nn));
bef[nn]=cd; // bef 노드 업데이트: nn을 방문하기 직전에 cn을 방문한다
}
}
}
//이후는 생략
return 0;
}
두 줄 추가했다. 바로 bef[]라는 배열을 추가한 것이다.
nn번 노드를 방문하는 최단 경로가 cn과 nn을 잇는 간선을 포함한다면, nn번 노드 방문 직전에 cn번 노드를 방문했을 것이다.
그러면 bef[nn]=cn 이렇게 저장해준다.
그리고 도착지 노드로부터 bef[]배열을 이용해서 그 직전에 방문한 노드를 하나씩 역추적해가면 경로 자체를 복원할 수도 있다.
예시) 1 -> 8번 노드를 잇는 최단 경로를 찾자.
bef[8]=7이다 => 1 -> 7번 노드를 잇는 최단 경로를 찾자.
bef[7]=3이다 => 1 -> 3번 노드를 잇는 최단 경로를 찾자.
bef[3]=1이다
=> 1 -> 8을 잇는 최단 경로는 1 -> 3 -> 7 -> 8 이 된다.
최단 경로의 경유지를 파악해서 그를 이용해 경로 전체를 알아낸다는 점에서 플로이드 워셜 알고리즘에서 경로 복원하는 방식이랑 비슷하다.
그런데, 이 방식으로는 최단 경로 중 하나만 알아낼 수 있다.
비용이 한은 여러 가지 경로들이 있다면 전부 다 알 수는 없는 것이다.
if(nd<dis[nn])
{
dis[nn]=nd;
pq.push(pii(-nd,nn));
bef[nn]=cd; // bef 노드 업데이트: nn을 방문하기 직전에 cn을 방문한다
}
바로 이 부분 때문이다.
if문 안에 부등호가 <=가 아니고 < 이다.
새로 찾은 특정 노드를 도착지로 하는 최단 경로가 기존에 찾았던 경로보다 작은 때만 업데이트를 해준다.
그럼 ==인 경우도 추가한다면 답을 찾을 수 있지 않을까?
그렇다.
다만 코드 수정이 조금 필요하다. int 배열인 bef[] 배열은 숫자 하나만 저장할 수 있기 때문이다.
그래서 int가 아닌 vector 배열으로 수정해보자.
코드 C
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#define NMAX 1500
using namespace std;
typedef pair<int, int> pii;
int main()
{
int v,e;
cin>>v>>e;
int k;
cin>>k;
vector<pii> rd[NMAX]; // road
vector<int> bef[NMAX]; // bef 배열: 특정 노드를 최단 경로를 따라 이동했을 때 그 노드 직전에 방문한 노드
for(int i=0;i<e;i++)
{
int u,v,w;
cin>>u>>v>>w;
rd[u].push_back(pii(v,w));
}
int dis[NMAX];
for(int i=1;i<=v;i++)
{
dis[i]=INT_MAX;
}
dis[k]=0;
priority_queue<pii> pq;
pq.push(pii(-0,k));
while(!pq.empty())
{
pii x=pq.top();
pq.pop();
int cn=x.second; // current node
int cd=-x.first; // current distance
if(cd>dis[cn])
{
continue;
}
for(auto j:rd[cn])
{
int nn=j.first; // next node
int nd=cd+j.second; // next distance
if(nd<dis[nn])
{
dis[nn]=nd;
pq.push(pii(-nd,nn));
bef[nn].clear();
bef[nn].push_back(cd); // bef 노드 업데이트: nn을 방문하기 직전에 cn을 방문한다
}
else if(nd==dis[nn])
{
bef[nn].push_back(cd);
}
}
}
//이후는 생략
return 0;
}
bef[] 배열은 이제 특정 노드를 방문하기 직전에 방문해도 되는 노드들의 목록이다.
예시)
1 -> 8 로의 최단 경로가
1 -> 7 -> 8
1 -> 4 -> 8
이렇게 두 개가 존재한다면,
bef[8]은 {4, 7} 이렇게 4와 7 두 숫자가 저장된 vector이다.
이와 같은 그래프를 상정해보자.
1번 노드에서 5번 노드로 가는 최단 경로를 찾고자 한다.
최단 경로는 다음과 같다.
최단 경로는 2가지가 있다. 4번 노드를 경유하는 빨간 경로, 그리고 2번 노드와 3번 노드를 경유하는 분홍 경로.
자, 그래프 A에 대한 간선들의 정보는 rd[] 배열이 가지고 있다.
rd[x]는 x에서 출발하는 모든 간선들의 도착노드와 그 비용에 대한 정보가 담겨져 있다.
그렇다면 bef[] 배열은 과연 어떤 그래프의 간선들에 대한 정보를 가지고 있을까?
바로 그래프 C가 된다.
1과 5를 잇는 최단 경로들에 포함된 모든 간선들을 저장해둔 것이 바로 bef[] 배열인 것이다! (다만 방향이 거꾸로이므로 역추적을 통해 경로를 복원해야 한다)
자, 다익스트라 알고리즘을 이용해 두 노드를 잇는 모든 최단거리들을 복원하는 데 성공했다.
2부: 또다른 방법을 시험해보자.
새로운 방법을 하나 제안해보겠다.
코드는 다음과 같다.
코드 D
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#define NMAX 1500
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> pip;
int main()
{
int v,e;
cin>>v>>e;
int k;
cin>>k;
vector<pii> rd[NMAX]; // road
int nex[NMAX]; // nex배열: bef 배열의 반대라고 생각하자.
for(int i=0;i<e;i++)
{
int u,v,w;
cin>>u>>v>>w;
rd[u].push_back(pii(v,w));
}
int dis[NMAX];
for(int i=1;i<=v;i++)
{
dis[i]=INT_MAX;
}
dis[k]=0;
priority_queue<pip> pq; // pii 대신 pip를 사용, 숫자 3개를 동시에 저장함
pq.push(pip(-0,pii(k,0)));
while(!pq.empty())
{
pip x=pq.top();
pq.pop();
int cn=x.second.first; // current node
int cd=-x.first; // current distance
if(cd>dis[cn])
{
continue;
}
nex[cn]=x.second.second;
for(auto j:rd[cn])
{
int nn=j.first; // next node
int nd=cd+j.second; // next distance
if(nd<dis[nn])
{
dis[nn]=nd;
pq.push(pip(-nd,pii(nn,cn)));
}
}
}
//이후는 생략
return 0;
}직전에 방문한 노드에 대한 정보를 bef 배열이 아니라 pq에 노드를 push 할 때 같이 집어넣는 것이다.
그래서 숫자 2개를 저장하는 pii가 아니라 pip 자료형을 이용한 우선순위 큐로 수정했다.
( pii와 pip는 내가 직접 정의한 자료형인데 코드 윗부분 typedef 쪽 참고)
그러면 pq에서 x를 꺼낼 때 x에는 노드와 최단 거리뿐만 아니라 그 이전에 방문한 노드에 대한 정보까지 들어있다.
이 방법을 이용한다면 장점은 bef[] 배열이 아니라 nex[] 배열을 만들 수 있다.
기존에 bef[]를 이용했을 땐 도착 노드에서 시작해 출발 노드까지 최단 경로를 역추적했는데, 최단 경로를 역추적할 필요가 없이 출발 노드에서 시작해 도착지까지 최단 거리로 가는 경로를 정 순서대로 찾을 수 있다.
역시나 이는 최단 경로 중 단 하나만을 찾아주는 알고리즘이다. 그러니 다음과 같이 수정해 모든 최단 경로를 찾아주도록 바꾸자.
코드 E
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#define NMAX 1500
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> pip;
int main()
{
int v,e;
cin>>v>>e;
int k;
cin>>k;
vector<pii> rd[NMAX]; // road
vector<int> nex[NMAX]; // nex배열: bef 배열의 반대라고 생각하자.
for(int i=0;i<e;i++)
{
int u,v,w;
cin>>u>>v>>w;
rd[u].push_back(pii(v,w));
}
int dis[NMAX];
for(int i=1;i<=v;i++)
{
dis[i]=INT_MAX;
}
dis[k]=0;
priority_queue<pip> pq; // pii 대신 pip를 사용, 숫자 3개를 동시에 저장함
pq.push(pip(-0,pii(k,0)));
while(!pq.empty())
{
pip x=pq.top();
pq.pop();
int cn=x.second.first; // current node
int cd=-x.first; // current distance
if(cd>dis[cn])
{
continue;
}
nex[cn].push_back(x.second.second);
for(auto j:rd[cn])
{
int nn=j.first; // next node
int nd=cd+j.second; // next distance
if(nd<=dis[nn]) // 부등호 <를 <=로 수정
{
dis[nn]=nd;
pq.push(pip(-nd,pii(nn,cn)));
}
}
}
//이후는 생략
return 0;
}
nex[] 배열이 vector 배열로 바뀐 것과 더불어, 또 하나의 차이점은 바로 이 부분이다.
if(nd<=dis[nn]) // 부등호 <를 <=로 수정
{
dis[nn]=nd;
pq.push(pip(-nd,pii(nn,cn)));
}
부등호를 <=로 바꾼 것이다.
두 가지 경로가 비용이 같다면 두 경로 다 우선순위 큐에 삽입한다.
이로써 최단 경로를 전부 구할 수 있는가?
일단, 정답은 그렇다 이다.
하지만 틀린 방법이라고도 할 수 있겠다.
특정한 경우에서 시간이 너무 오래 걸리기 때문이다.
백준에서 문제를 풀다보면 최단 경로들을 전부 구해야 하는 문제들이 있다.
최단 경로들 중에서도 특정 추가 조건을 만족하는 경로를 구해야한다든가... 등 말이다.
이를 테면 이 문제, 9370번 미확인 도착지 문제
https://www.acmicpc.net/problem/9370
이 문제는 최단 경로들 중에서 g와 h를 잇는 간선을 지나는 경로가 있는가를 확인하는 문제이므로, 모든 최단 경로들을 다 확인해보아야 한다.
백준에서 이런 문제들을 코드 E와 같은 방식으로 푼다면 아마도 메모리 초과 또는 시간 초과가 날 것이다.
극단적인 예시로 그래프 D를 가져와보겠다.
(모든 간선의 비용은 1이라고 하자)
1번 노드가 출발지이다.
2번 노드로 가는 최단 경로는 2가지
3번 노드로 가는 최단 경로는 4가지
....
8번 노드로 가는 최단 경로는 2^7가지
이런 식으로 간선의 개수에 대해 지수적으로 최단 경로의 개수가 늘어난다.
그런데 이러한 모든 최단 경로들에 대해 전부 다 우선순위 큐에 넣게 된다.
간선이 E개라면 우선순위 큐 안에 O(2^E)개 만큼 값이 들어가는 것이다. 메모리가 충분하지 않다면 메모리 초과가 날 것이고, 그렇지 않더라도 우선순위 큐 안에 push와 pop을 하는 과정에서 시간 초과가 날 것이다.
이를 방지하려면 어떻게 해야 할까?
어떤 식이든,
if(nd<=dis[nn]) // 부등호 <를 <=로 수정
{
dis[nn]=nd;
pq.push(pip(-nd,pii(nn,cn)));
}
이처럼 부등호를 단순히 <에서 <=로 바꿔선 안된다는 것이다. 모든 최단 경로들에 대해 전부 우선순위 큐에 삽입하게 되기 때문이다.
그러니 코드 C와 같은 방식을 사용하자.
if(nd<dis[nn])
{
dis[nn]=nd;
pq.push(pii(-nd,nn));
bef[nn].clear();
bef[nn].push_back(cd); // bef 노드 업데이트: nn을 방문하기 직전에 cn을 방문한다
}
else if(nd==dis[nn])
{
bef[nn].push_back(cd);
}
<를 단순히 <=로 바꾸지 말고 < 인 경우와 ==인 경우로 나누는 것이다.
핵심은 ==인 경우엔 우선순위 큐에 push를 하면 안된다는 것이다. push를 한다면 이는 최단 경로를 전부( O(2^E)개 )를 우선순위 큐에 push하는 것과 같다. 메모리 초과가 날 수가 있다. 직전 노드에 대한 정보를 추가만 해주어야 한다.
구현은 자유지만 나는 bef[] 배열로 구현한 방법을 보여주었다.
다익스크라 변형 문제를 풀다가 메모리 초과가 났다면 이 경우를 의심해 보아라.
챌린지: 모든 최단 경로를 구해야 하는 문제 백준 5719번 거의 최단 경로를 풀어보자. https://www.acmicpc.net/problem/5719
정리:
코드 A는 최단 거리를 구해준다.
코드 B는 최단 경로 중 하나를 구해준다.
코드 C는 최단 경로를 전부 구해준다.
코드 D는 최단 경로 중 하나를 구해준다.
코드 E는 최단 경로를 전부 구해주지만, 비효율적인 코드이다.
'공부 > 코딩' 카테고리의 다른 글
| FWA 2부: 플로이드 워셜 알고리즘에서 경로 복원하기 (0) | 2025.03.08 |
|---|---|
| FWA 1부: 플로이드-워셜 알고리즘과 주의사항 (반복문의 순서가 중요한 이유) (0) | 2025.03.06 |
| 고려대학교의 마이크로디그리 제도 (0) | 2025.02.16 |
| [C++] 코딩할때 '\b' 문자에 관하여 (1) | 2024.12.15 |
| 게일 섀플리 알고리즘(Gale–Shapley algorithm) (1) | 2024.11.10 |