---

两种算法本质是相同的。

都是从某一个点开始进行延伸，不断更新一个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所在）

struct point{    int hao;    ll dis;    bool friend operator <(point a,point b)    {        return a.dis>b.dis;    }};priority_queue
     
      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所在）

struct point{    int dis,hao;    bool friend operator <(point a,point b)    {        return a.dis>b.dis;    }};priority_queue
     
      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可以。