dij与prim算法
枫林晚
2018-05-08 15:56:33
两种算法本质是相同的。
都是从某一个点开始进行延伸，不断更新一个dis值，直到所有的点都被遍历到，从而求出一个最短路或者是一个树的边权的最小总和。
朴素算法都是n^2，都可以采用堆优化处理，降低复杂度到mlogn.
但是在一张完全图上跑，此时m=n^2，朴素算法反而快一些。而且常数小。
相比较于SPFA，dij可以稳定的mlogn 或者 n^2.
SPFA理论上是KE，但是完全图上E=n^2,直接多乘了一个k，而且传说卡SPFA是比较好卡的。所以图比较疏密的时候，dij能用，就用dij。
SPFA最大的优点就是可以处理负边权。
dij代码核心：（堆优化）
朴素时候，直接扔掉优先队列，循环一遍找最小dis值。（也是n^2所在）
```cpp
struct point{
int hao;
ll dis;
bool friend operator <(point a,point b)
{
return a.dis>b.dis;
}
};
priority_queue<point>q;
void dij()
{
point st;
st.hao=s;
st.dis=0;
q.push(st);
int has=0;
while((has!=n)&&(!q.empty()))
{
point now=q.top();
q.pop();
if(vis[now.hao]) continue;
has++;
vis[now.hao]=1;
dis[now.hao]=now.dis;
for(int i=head[now.hao];i;i=bian[i].nxt)
{
int y=bian[i].to;
if(!vis[y])
{
point last;
last.hao=y;
last.dis=now.dis+bian[i].val;
q.push(last);
}
}
}
}
```
prim与kruskal比较，其优点也是在完全图上有稳定的复杂度n^2.
prim也可以用堆优化，但是完全图上同样也是朴素更快。
kruskal的复杂度局限在于排序。mlogm直接送出。m=n^2慢炸。
代码核心：（堆优化）
朴素时候，直接扔掉优先队列，循环一遍找最小dis值。（也是n^2所在）
```cpp
struct point{
int dis,hao;
bool friend operator <(point a,point b)
{
return a.dis>b.dis;
}
};
priority_queue<point>q;
int n,m;
int sum;
bool vis[N];
bool work()
{
point now;
now.hao=1;
now.dis=0;
int has=0;
q.push(now);
while(has!=n&&(!q.empty()))
{
point now=q.top();q.pop();
if(vis[now.hao]) continue;
vis[now.hao]=1;has++;
sum+=now.dis;
for(int i=head[now.hao];i;i=bian[i].nxt)
{
int y=bian[i].to;
if(!vis[y])
{
point kk;
kk.hao=y;
kk.dis=bian[i].val;
q.push(kk);
}
}
}
if(has==n) return true;
return false;
}
```
总结：
1.SPFA,kruskal在稀疏图上有优势。
2.dij，prim稠密图上占优。
3.dij不能处理负边权，SPFA可以。