最短路问题

2023-12-01 09:31:16

常见的求最短路方法

1.单源最短路

给定一个带权有向图G=（V，E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。要算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和这个问题通常称为单源最短路问题。

1.1仅含正权边

1.1.1 Dijkstra算法

思想：

将图中所有点分为两部分，以v为源点并且确定了最短路径的点为集合S，刚开始集合S只包含v，另一部分是到源点距离还未确定的点的集合T。然后每次找到T中某个a点到v点距离最短，把a点加入到集合S中，再用a点到v点的距离去更新T中剩余点到v的距离，直到T为空。

const int N=510;
int g[N][N];//两点之间的距离
int n,m;//n个点数字为代号，m条边
int dist[N];//存储点到原点的距离
bool st[N];//判断点是否在集合S中
int Dijkstra(){
    memset(dist,0x3f,sizeof dist);//将点到源点的距离初始化无穷大
    dist[1]=0;//源点为1，1到自己的距离为0
    for(int i=0;i<n;i++)//循环n次是因为点有n个将他们挪到S中去需要n次
    {
        int t=-1;//t为T中距离到v最短点
        for(int j=1;j<=n;j++)//循环n次是为了找到T中距离1最短的点
            if(!st[j]&&(t==-1||dist[j]<dist[t]))
            t=j;//找到离源点1距离最短的点
            st[t]=true;//将这个点加入到集合S中
        for(int k=1;k<=n;k++)
        dist[k]=min(dist[k],dist[t]+g[t][k]);//用这个点更新其他点，因为S中其他点已经是最短距离t不会更新这些点
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    else
    return dist[n];
}

可以看到朴素版Dijkstra算法时间消耗在找到T中到v最短的点，可以用小根堆来优化，堆中元素即为集合T中的点，堆顶元素为到v距离最短的点。

const int N=1e6;
typedef pair<int, int> PII;
int n,m;//n个点，m条边（m没用，用来控制输入的）
int h[N], e[N], ne[N], idx;//用邻接表存储图
int w[N];//两个点之间的权重
int dist[N];//点到源点1的距离
bool st[N];//集合S
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()  // 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
{memset  (dist,0x3f,sizeof(dist));
priority_queue<PII,vector<PII>,greater<PII>> heap;//小根堆
dist[1]=0;
heap.push({0,1});//first是到源点1的距离，second是点，先只将1放入堆中，其余点会在后面被更新，更新后会放入堆中
while(heap.size()){//堆不为空说明T不为空
    PII t=heap.top();//堆顶始终是集合T中到源点1距离最短的点
    heap.pop();//从集合T中删除该点
    int var=t.second,distance=t.first;
    if(st[var])continue;
    st[var]=true;//将该点加入集合S
    for(int i=h[var];i!=-1;i=ne[i]){
        int j=e[i];
        if(dist[j]>distance+w[i])
        {
            dist[j]=distance+w[i];
            heap.push({dist[j],j});//点被更新加入集合T
        }
    }
}

    if(dist[n]==0x3f3f3f3f)return -1;
    else return dist[n];
    
}

1.2 存在负权边

1.2.1 bellman-ford 算法

当图中有负权边时Dijkstra算法就无能为力了，但是bellman-ford算法可以解决这个问题

思想：

该算法基于动态规划，反复用以有的边来更新最短距离，核心思想是松弛。假设有n个点，设有点a，如果有某点b使dist[a]>dist[b]+w[a](b点到a点边的权重），就更新dist[a]，反复改变b点对dist数组进行松弛，如果没有负权回路的话会在n-1次松弛后结束。

const int N=510;
const int M=10010;
struct Edge{
    int a;
    int b;
    int w;
}e[M];//bellmam-ford算法只要能遍历每条边就行，可以用结构体存储
int dist[N];//点到源点1的距离
int backup[N];//给dist数组备份一下，后面讲为啥
int n,m,k;//n点的个数，m边数，k控制路径长度，最多经过多少条边到某点
int bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1]=0;
    while (k -- ){
        memcpy(backup,dist,sizeof dist);//备份数组dist是为了避免当k=1时出现串联的情况，如下图当k=1，dist[2]更新为1后dist[3]会被更新为2，但是却走了两条边，因此要用dist[2]未被更新时的数来更新dist[3]为无穷；
        for(int i=0;i<m;i++){
            int a=e[i].a;
            int b=e[i].b;
            int w=e[i].w;
            if(dist[b]>backup[a]+w)
            dist[b]=backup[a]+w;
        }
    }
    if(dist[n]>0x3f3f3f3f/2) return  0;//这里只用大于0x3f3f3f3f/2是因为当某个a点到1的距离为无穷远，a到n的距离为-2，dist[n]<0x3f3f3f3f
    else
    return dist[n];
}

1.2.2 spfa算法

spfa算法是对bellman-ford算法的优化。bellman-ford算法会遍历所有的点，但是实际上只用遍历那些前驱节点被更新的点，因此可以用队列来存储这些被更新的点，因此用spfa算法要求图中不能含有负权回路，有负权回路就会一直有点被更新，算法会陷入死循环，但可以用spfa算法来判断负权回路，设有n个点，用cnt数组记录每个点到源点的边数，当某个点cnt=n就证明有负环。spfa算法和Dijkstra算法看起来很相似其实还是有一定的区别。spfa算法中队列用来存被更新的点，st数组是判断点是否在队列中，如果在队列中不用入队只用更新dist，Dijkstra算法中的优先队列中是未确定最短距离的点，st数组是已经确定最短距离的点。

const int N = 1e5+10;
int h[N], e[N], ne[N], idx;
int w[N];
int dist[N];
bool st[N];//点是否在队列中
int n,m;
void add(int a, int b, int c)  
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int SPFA(){//要求图中没有负权回路
    memset(dist,0x3f,sizeof dist);
    queue<int> q;
    dist[1]=0;
    st[1]=true;
    q.push(1);
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;//出队后t点还可以被更新，只要队列中还有元素就没有确定最短距离，Dijkstra算法中t出堆后就确定了最短距离
        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]){
                st[j]=true;
                q.push(j);
            }
                
            }
        }
    }
    if(dist[n]>0x3f3f3f3f/2)return 0;
    else
    return dist[n];
}

spfa算法判断负权回路

const int N = 1e5;
int h[N], e[N], w[N], ne[N], idx;
int q[N], dist[N];
int cnt[N];
bool st[N];
int n,m;
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool spfa()  // 如果存在负环，则返回true，否则返回false。
{
    // 不需要初始化dist数组，当有负权回路时，某个值dist会不断减小
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，
    // 由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for(int i=1;i<=n;i++)
    q.push(i);//将点全部入队是因为可能有点不连通
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        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];
                cnt[j]=cnt[t]+1;//到j点的边数加1
                if(cnt[j]>n)
                return true;
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
                
            }
            
        }
    }
    return false;
}

2.多源最短路

多源最短路就是指每一个点到图中其他顶点的最短路

floyd算法来求多元最短路（证明可以自行百度）

int d[N][N];//两点之间的距离
void floyd(){
    for(int k=1;k<=n;k++)//n个点
     for (int i = 1; i <= n; i ++ )
      for(int j=1;j<=n;j++)
      d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

码农公寓