最短路算法整理 七七八八的总结

最短路算法整理

1.Dijkstra 算法

先讲讲朴素的Dijkstra算法的思路.朴素的Dijkstra算法先将起点入队.然后找到一个起点距离最近的点.再用这个点去更新其他所有的点.一共有多少个点就进行多少次迭代.因为每次找到一个用于更新距离的点.它的最短距离就已经确定了.

核心代码:

#include <iostream>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f
const int N = 510;
int n,m,g[N][N],st[N],dist[N];
void dijkstra()
{
    fill(dist,dist+N,INF);
    dist[1] = 0;
    for(int i=1;i<=n;i++)
    {
        int t = -1;//第一次t一定 = 起点
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[j]<dist[t])) t = j;//确定距离最短的点
        for(int j=1;j<=n;j++)
            dist[j] = min(dist[t]+g[t][j],dist[j]);//更新其他距离
        st[t] = 1;
    }
    if(dist[n]==INF) printf("-1\n");
    else printf("%d\n",dist[n]);
}

这种方法复杂度很高,需要优化.因为第一个j循环本质是找到当前距离最小的点,所以可以用优先队列优化.dijkstra的st数组表示的是当前点的最短距离是否被确定.

因此出现了堆优化版的dijkstra算法.

核心代码:

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;//dist[i]表示起点到i的距离
    priority_queue<pii,vector<pii>,greater<pii> > q;//存储的是距离 与谁的距离
    q.push({0,1});
    while(q.size())
    {
        auto it = q.top();
        q.pop();
        if(st[it.second]) continue;
        st[it.second] = 1;
        for(int i=h[it.second];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dist[it.second]+w[i]<dist[j]) { dist[j] = dist[it.second]+w[i]; q.push({dist[j],j});}
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

每次st数组被标为1,说明当前点的最短距离已经确定了.

Dijkstra的优点是某些卡SPFA的题它不会被卡.所以单源最短路优先用Dijkstra.

时间复杂度O(m l o g 2 n log_2 n log2​n)

2.SPFA 算法

这个算法与Dijkstra算法十分相似.但它本质是对BF算法的一个优化.BF算法每次枚举一个点,再用所有的点去更新当前点的最短距离.SPFA算法就是对其进行了优化.它的核心思想是对于当前队头,将它所有能更新的点入队.反复此过程直到不能更新了为止.

这里的st数组表示当前点是否在队列中.

核心代码:

void spfa(int s)
{
    fill(dist,dist+N,0x3f3f3f3f);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    st[s] = 1;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = 0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j] = dist[t]+w[i];//写在外面,应为相同点对应边不同也可以更新距离
                if(!st[j]) q.push(j),st[j] = 1;
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) printf("impossible\n");
    else printf("%d\n",dist[n]);
}

因为st数组的值在反复变化,并且队列也不是按距离进行排序.所以每个点都有多次入队的机会.如果用数组实现队列需要用循环队列.

时间复杂度O(m) m指边的数量.

因为队列可以多次入队同一点.所以SPFA算法可以用来处理负边权和判负环.

cnt数组表示入队次数,也就是有多少边能到此点.如果cnt[t]>n 说明出现了环.

核心代码:

bool spfa(int n)
{
    queue<int> q;
    for(int i=1;i<=n;i++) { q.push(i); st[i] = 1;}
    while(q.size())//如果存在负环,到路径上最后一个点->初始点d<=0,所以可以继续更新.
    {//初始点进入时,其他点的st都被置0
        int t = q.front();
        q.pop();
        st[t] = 0;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dist[j]>dist[t]+w[i])
            {
                cnt[j] = cnt[t]+1;//放外面的原因应该是如果队列里还有更短的路径可到j,更方便更新
                if(cnt[j]>n) return true;
                dist[j] = dist[t]+w[i];
                if(!st[j]) q.push(j),st[j] = 1;
            }
        }
    }
    return false;
}