特殊最短路

  • 树：直接起点dfs搜索到终点即可
  • 有向无环图：拓扑排序，删掉每一个点时更新后继的最短距离
  • 边权全部为相等：bfs

单源最短路

  • 从一个点出发到其它顶点的最短路径长度
  • 基本操作：松弛
  • 这样的(u,v)称为紧的，可以对它进行松弛

dijkstra

  • 不能存在负边，每个边会被访问一次，每个边都有可能进一次优先队列
  1. dis数组初值赋为极大
  2. 起点dis为0
  3. 计算与s相邻的所有点的dis——
  4. 取还没算出最短路的点中dis最小的点u，它的最短路就是
  5. 对于u相连的所有点v如果能松弛，更新
  6. 重复4,5直到所有点求完
#include<bits/stdc++.h>
using namespace std;


typedef struct{
    int t,l,nxt;
}E;

struct ty{
    int x,dis;
    bool operator < (const ty &a) const{
        return dis > a.dis;
    }
};

E edge[101010];
int n,m,s,t;
int dis[1010],vis[1010];
int head[1010];
int cnt=0;

void insert(int x,int y,int val){
    edge[++cnt].t=y;
    edge[cnt].l=val;
    edge[cnt].nxt=head[x];
    head[x]=cnt;

}

priority_queue<ty> q;
int dijkstra(int st,int to){
    dis[st]=0;
    ty tmp;
    tmp.x=s,tmp.dis=0;
    q.push(tmp);
    while(!q.empty()){
        ty tp=q.top();
        q.pop();
        if(vis[tp.x]) continue;
        vis[tp.x]=1;
        for(int i=head[tp.x];i!=-1;i=edge[i].nxt){
            int to=edge[i].t;
            if(vis[to]) continue;
            if(dis[to]>dis[tp.x]+edge[i].l){
                dis[to]=dis[tp.x]+edge[i].l;
                ty tp2;
                tp2.x=to,tp2.dis=dis[to];
                q.push(tp2);
            }
        }

    }
    if(dis[t]>=0x3f3f3f3f) return -1;
    else return dis[to];
}

int main(){
    cin >> n >> m >> s >> t;
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++){
        int a,b,v;
        cin >> a >> b >> v;
        insert(a,b,v);
        insert(b,a,v);
    }
    cout << dijkstra(s,t) << endl;

    return 0;
}

Bellman-Ford

  • 可以有负边，不能有负环(环上所有边权值和不能为负)
  • 枚举所有点，能松弛就松弛，直到所有点都不能松弛
//邻接矩阵,O(n^3)
while(b){
    b=false;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dis[j]+val[j][i]<dis[i]){
                dis[i]=dis[j]+val[j][i];
                b=true;
            }
        }
    }
}

SPFA--BF的队列优化(O(KM),K为平均入队次数,只有有负权才用)

  • dis数组表示距离，fa数组表示s到i的最短路径中到i的前一个点，fa初值为0,dis初值为极大，dis[s]=0
  • 维护一个队列，存放需要迭代的点，初始时队列里只有一个s
  • 维护一个bool数组，记录每一个点是否在队列中
  • 每次取出队首v，枚举v发出的边v->u，长度为len，如果dis[v]+len<dis[u]则改进dis[u]同时，fa[u]=v
  • 由于s到u的距离变小了，所以u有可能改进其它点，所以如果u不在队列中，将u弹入队尾
  • 循环这个过程，直到队列为空，如果任意一个点入队次数超过n，则存在负权环
#include<bits/stdc++.h>

using namespace std;

typedef struct{
    int t,l,nxt;
}E;

E edge[101010];
int head[101010];
int cnt;
int n,m,s,t;
int dis[1010],vis[1010];

void insert(int x,int y,int val){
    edge[++cnt].t=y;
    edge[cnt].l=val;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}

queue<int> q;
int spfa(int s,int t){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i!=-1;i=edge[i].nxt){
            int y=edge[i].t;
            if(dis[y]>dis[x]+edge[i].l){
                dis[y]=dis[x]+edge[i].l;
                if(!vis[y]){
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
    if(dis[t]>=0x3f3f3f3f) return -1;
    else return dis[t];
}

int main(){
    cin >> n >> m >> s >> t;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++){
        int a,b,v;
        cin >> a >> b >> v;
        insert(a,b,v);
        insert(b,a,v);
    }
    cout << spfa(s,t) << endl;
    return 0;
}

多源最短路

Floyd

for(int k=1;k<=n;k++){//中转点一个个往里加
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j&&j!=k&&k!=i){
                if(f[i][k]+f[k][j]<=f[i][j]){
                    f[i][j]=f[i][k]+f[k][j];
                }
            }
        }
    }
}