寒假训练Day2-2024.01.27

一,Dijkstra算法（迪杰斯特拉算法）
时间复杂度为O (N2)。
用dis[i]来存储i点到起点v0最短路径，初始化dis[i]=e[v0][i]。
用s[i]来存储i点是否在集合s（0表示不在，1表示在）。
用pash[i]来存储i点的前驱。
在Dijkstra中，重复执行以下三步：
1. 找到不在集合s中，距离v0最近的点k。
**2. 把s[k]设为1。
3. 修其他顶点j的dis和path数组元素值。当s[j]0，且dis[k]+e[k][ j]<dis[j]，将dis[j]改为dis[k]+e[k][j]，将path[j]改为k。
代码如下：

#include<bits/stdc++.h>
using namespace std;
//定义
const int N=10010;
int n,m;
int e[N][N];//存储两点之间的距离
int dis[N],s[N],path[N];
int Dijkstra(){
    memset(dis,0x7f,sizeof(dis)); //初始化
    dis[1]=0;
    for(int i=0;i<n;i++){
        int t=-1; //寻找到dis中最小且还没被标记过的点
        for(int j=1;j<=n;j++){
            if(!s[j]&&(t==-1||dis[t]>dis[j])){
               t=j;
            }
        }
        s[t]=true;//标记点t已经找到最短路径了
        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],dis[t]+e[t][j]);//通过点t中转
        }
    }
    if(dis[n]==0x7f)return -1;//无法到达n输出-1
    return dis[n];
}
int main(){
    cin>>n>>m;
    memset(e,0x7f,sizeof(e));//初始化
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e[a][b]=e[a][b]=min(e[a][b],c);
    }//读入数据
    cout<<Dijkstra()<<endl;//可以堆优化
    return 0;
}

二,Bellman-Ford算法（贝尔曼-福特算法）
时间复杂度为O(nm)。
用dis[i]来存储i点到起点v0最短路径，初始化dis[i]=e[v0][i]。
用pash[i]来存储i点的前驱。
用u[j]，v[j],w[i]来表示从顶点u[i]到顶点v[i]的权值为w[i]。
执行n-1次，每次对所有的边进行松弛。
代码如下：

#include<bits/stdc++.h>
using namespace std;
//定义
const int N=10010;
int n,m;
int e[N][N];//存储两点之间的距离
int dis[N],path[N],u[N],v[N],w[N];
int main(){
    //读入和初始化
    cin>>n>>m;
    memset(dis,0x7f,sizeof(dis));
    memset(path,-1,sizeof(path));
    dis[1]=0;
    //Bellman-Ford核心代码
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        path[v[i]]=u[i];//v[i]的前驱是u[i]
    }
    for(int k=1;k<n;k++){//进行n-1轮松弛
        for(int i=1;i<=m;i++){//枚举所有边，判断能否松弛
            if(dis[u[i]]+w[i]<dis[v[i]]){
               dis[v[i]]=dis[u[i]]+w[i];
               path[v[i]]=u[i];
            }
        }
    }
    cout<<dis[n];
    return 0;
}

Bellman-Ford核心代码优化：

for(int k=1;k<n;k++){//进行n-1轮松弛
    bool flag;
    for(int i=1;i<=m;i++){//枚举所有边，判断能否松弛
        if(dis[u[i]]+w[i]<dis[v[i]]){
           dis[v[i]]=dis[u[i]]+w[i];
           path[v[i]]=u[i];
            flag=true;
        }
    }
    if(!flag)break;
}

三,SPFA算法（Bellman-Ford优化）
时间复杂度为O(km)（一般k<=2）
用队列来存储有变化的点（队列为空循环结束）。