원래 Dijkstra는 n^2의 시간 복잡도를 가지고 있지요.
하지만 이 Dijkstra함수는 E log V(E = 간선, V = 정점)의 시간복잡도를 가지고 있어서....
대부분의 경우 n^2보다 훨씬 빠른 속도를 출력합니다.
(다만 완전 그래프같이 E가 엄청나게 많은 경우에는 예외 -_-;;;)
힙을 써서 구현했습니다.
#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;
class node{
public:
int pp;
int data;
bool operator > (node right)
{
return data > right.data;
}
bool operator < (node right)
{
return data < right.data;
}
bool operator >= (node right)
{
return data >= right.data;
}
bool operator <= (node right)
{
return data <= right.data;
}
};
vector<node> list[501];
/*
Vector에 데이터를 넣어준다.
끝점과 가중치를 넣을 때는
node 임시변수; 를 만들고
임시변수.pp = 끝점
임시변수.data=가중치
로 대입한뒤 list[시작점].push_back(임시변수)로 하면 리스트가 만들어진다.
*/
int pos[501]; /* 정점의 힙 내부의 위치를 나타내는 배열 */
template <typename T>
inline void swaps(T &a, T &b) /* SWAP 함수 */
{
T t = a;
a = b;
b = t;
}
template <typename T>
class min_heap{ /* Min_HEAP를 구현한 클래스이다. MIN HEAP는 다 알테니 생략. */
public: /* 사실 Priority_queue를 이용해도 되지만 클래스 예제와 힙 직접 구현 연습을 위해 직접 구현했다. */
T data[501];
int heapcnt;
T ms;
min_heap()
{
heapcnt=0;
};
/* Functions */
void push(T v)
{
data[++heapcnt]=v;
int p=heapcnt;
while(1)
{
if(p==1)
break;
if(data[p/2]>data[p])
{
swaps(pos[data[p/2].pp],pos[data[p].pp]);
swaps(data[p/2],data[p]);
//swap(1,2);
p /= 2;
}
else
break;
}
}
T top()
{
return data[1];
}
void pop()
{
if(heapcnt==0) return;
int p=1;
data[1]=data[heapcnt];
data[heapcnt]=ms;
heapcnt--;
while(1)
{
if(heapcnt/2<p) break;
if(p*2>heapcnt) continue;
if(p*2+1>heapcnt)
{
if(data[p*2]<data[p])
{
swaps(pos[data[p*2].pp],pos[data[p].pp]);
swaps(data[p*2],data[p]);
}
break;
}
if(data[p*2] <= data[p*2+1] && data[p*2] < data[p])
{
swaps(pos[data[p*2].pp],pos[data[p].pp]);
swaps(data[p*2],data[p]);
p *= 2;
}
else if(data[p*2] > data[p*2+1] && data[p*2+1] < data[p])
{
swaps(pos[data[p*2+1].pp],pos[data[p].pp]);
swaps(data[p*2+1],data[p]);
p=p*2+1;
}
else
{
break;
}
}
}
bool empty()
{
if(heapcnt==0)
return true;
return false;
}
int size()
{
return heapcnt;
}
void refresh(int p)
{
while(1)
{
if(heapcnt/2<p) break;
if(p*2>heapcnt) continue;
if(p*2+1>heapcnt)
{
if(data[p*2]<data[p])
{
swaps(pos[data[p*2].pp],pos[data[p].pp]);
swaps(data[p*2],data[p]);
}
break;
}
if(data[p*2] <= data[p*2+1] && data[p*2] < data[p])
{
swaps(pos[data[p*2].pp],pos[data[p].pp]);
swaps(data[p*2],data[p]);
p *= 2;
}
else if(data[p*2] > data[p*2+1] && data[p*2+1] < data[p])
{
swaps(pos[data[p*2+1].pp],pos[data[p].pp]);
swaps(data[p*2+1],data[p]);
p=p*2+1;
}
else
{
break;
}
}
}
/* End of Functions */
};
/*
여기까지가 힙 클래스. 사실 이 코드가 200줄 이상인 이유는 힙 클래스 때문이다 -_-;
힙클래스를 제외하고 쓸모없는 부분을 제외한다면 실제로 50줄 이내
*/
int dist[501][501]; // 최단거리를 저장하는 배열이다.
void dijkstra(int s) //E log V Dijkstra 부분이다. dijkstra(시작점)으로 호출을 하면 dist[시작점][끝점] 에 최단거리가 저장된다.
{
int i;
min_heap<node> heap; //MIN_HEAP
bool chk[501]; //체크 배열
int j;
for(i=1;i<=500;i++) //배열 초기화
{
dist[s][i]=0;
pos[i]=0;
chk[i]=0;
}
node tmp; //데이터를 push / pop하기 위한 임시 변수
for(i=0;i<list[s].size();i++) //시작점에서 갈수있는곳을 우선 힙에 저장.
{
tmp=list[s][i];
heap.push(tmp);
pos[tmp.pp]=heap.size();
chk[tmp.pp]=true;
}
for(i=1;i<=n;i++)
{
if(chk[i]==0 && i != s)
{
tmp.pp=i;
tmp.data=1000000001;
heap.push(tmp);
pos[i]=heap.size();
}
}
node tmp2; // 위의 node tmp와 같음.
for(i=1;i<n;i++)
{
tmp=heap.top();
pos[heap.data[heap.size()].pp]=1;
pos[1]=pos[heap.size()];
heap.pop();
dist[s][tmp.pp]=tmp.data;
for(j=0;j<list[tmp.pp].size();j++)
{
tmp2=list[tmp.pp][j];
if(pos[tmp2.pp] > 0 && heap.data[pos[tmp2.pp]].data > tmp.data + tmp2.data)
{
heap.data[pos[tmp2.pp]].data=tmp.data+tmp2.data;
heap.refresh(pos[tmp2.pp]);
}
}
}
}
