包含

• DijkstraI

• DijkstraII

• Bellman-Ford

• Floyd

DijkstraI

dijkstraI也叫朴素dijkstra，思路是在每一次查找时寻找距离原点最近且还未经过的点，并加入待处理的集合，以这点为中间节点，来遍历后面的节点，来确保路径是最短的。

适用于稠密图(n,m相差很大的情况下，否则用他的堆优化版本)、环。

不适用于有负权值的情况。

题目传送门： dijkstraI

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int e[N],ne[N],w[N],h[N],idx;//邻接表存图
int st[N];//判断这个点是否走过
int d[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++;
}

void dijkstra(){
  memset(d,0x3f,sizeof d);//初始化所有点到原点的距离为无穷大，方便后续判断是否可到
  d[1] = 0;//原点到原点的距离是0
  for(int i = 0;i < n;i++){//执行n次，每一次找出一个最短的点
    int t = -1;
    for(int j = 1;j <= n;j++){
      if(!st[j] && (t==-1 || d[j] < d[t])){//找过一次后最短点的st会更新，第二次就不会找他了
        t=j;
      }
    }

    st[t] = 1;//更新

    for(int j = h[t];j!=-1;j=ne[j]){//遍历以节点 t 为起点的所有边，更新这些边的终点到起点的最短距离
      int i = e[j];
      d[i] = min(d[i],d[t]+w[j]);
    }
  }
}

int main(){
  memset(h,-1,sizeof h);
  cin >> n >> m;
  for(int i = 0;i < m;i++){
    int a,b,c;
    cin >> a >> b >> c;
    add(a,b,c);
  }
  dijkstra();

  if(d[n] != 0x3f3f3f3f){//如果终点尚未呗更新说明到达不了终点。
    cout << d[n];
  }else{
    cout << -1;
  }

  return 0;
}

DijkstraII

根据dijkstraI可以看出来，再找最小点的时候，每次都要遍历，这里是可以优化的。

利用堆排序(priority_queue)来进行优化，可以省略遍历寻找最小的过程，直接输出最小点。

题目链接和上面共享一个吧，都差不多。

适用于稀疏图，也就是m，n差不多的情况下。

同样不适用于有负权边的情况

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5+10;
int e[N],ne[N],w[N],h[N],idx;
int st[N];
int d[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 dijkstra(){
  memset(d,0x3f,sizeof d);
  d[1] = 0;
  priority_queue<PII,vector<PII>,greater<PII>> p;//这里开了个小根堆
  p.push({0,1});//先把原点push进去，first是距离，second是点

  while(p.size()){//一直循环直到小根堆为空为止
    auto t = p.top();//拿出小根堆的堆顶（最小值）
    int ver = t.second;
    int dist = t.first;
    p.pop();//弹出

    if(st[ver]) continue;//如果这个点用过了就continue跳出这次循环
    st[ver] = 1;

    for(int i = h[ver];i != -1;i = ne[i]){//和dijkstraI同理，在最短进行广搜
      int j = e[i];

      //当 d[j] > d[ver] + w[i] 时，意味着当前记录的从源节点到节点 j 的最短距离 d[j]
      //大于从源节点经过节点 ver 再到节点 j
      //的距离。此时，说明找到了一条更短的路径，即经过节点 ver 到达节点 j
      //的路径比之前记录的路径更短，因此需要更新 d[j] 的值。

      if(d[j] > d[ver] + w[i]){//若经过当前节点到达终点的距离比当前记录的距离更短，则更新距离
        d[j] = d[ver] + w[i];//更新终点的最短距离
        p.push({d[j],j});//将更新后的终点及其距离加入优先队列
      }
    }
  }

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

int main(){
  memset(h,-1,sizeof h);
  cin >> n >> m;
  for(int i = 0;i < m;i++){
    int a,b,c;
    cin >> a >> b >> c;
    add(a,b,c);
  }

  cout << dijkstra() << endl;
  return 0;
}

Bellman-Ford

允许有负权边的情况

适用于限制步数、且有负权边的情况下

题目链接： 有边数限制的最短路

这道题与dijkstra不同的是他不需要看点周围能到达的其他点，只需要考虑每一条边即可

相当于只需要开一个结构体来储存起点终点和权值。

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int M = 10010;
int n,m,k;

struct Edge{//开一个结构体来记录每一条边
  int a;
  int b;
  int w;
}e[M];

int dist[N];//记录距离
int back[N];//备份上一次的距离

void bellman_ford(){
  memset(dist,0x3f,sizeof(dist));//初始化
  dist[1] = 0;//依旧原点到原点距离为0
  for(int i = 0;i < k;i++){//因为限制了k条边，所以在k条边后，到目标的距离如果没有更新，就是无法到达
    memcpy(back,dist,sizeof(dist));//备份这次的数据
    for(int j = 0;j < m;j++){
      int a = e[j].a,b=e[j].b,w=e[j].w;
      //这里用back是因为dist[a]可能是上一次循环的dist[b]，也就是说可能会发生过变化，所以用备份来算。
      dist[b] = min(dist[b],back[a]+w);//更新到b的最短路
    }
  }
  if(dist[n] > 0x3f3f3f3f / 2){//这里是/2是因为有负权边，导致d[x][y]更新了一下，不为INF了，有负权边统一大于无穷大一半就行
    cout << "impossible" << endl;
  }else{
    cout << dist[n] << endl;
  }
}

int main(){
  cin >> n >> m >> k;
  for(int i = 0;i < m;i++){
    int a,b,c;
    cin >> a >> b >> c;
    e[i]={a,b,c};//存入结构体
  }

  bellman_ford();
}

Folyd

folyd算是这哥四个最简单的了，他的问法也比较独特，不是从1~n，而是从a到b。如果是难题那不一定

会，但是数据范围给的小那就容易了，有点像暴力做法

原题链接： floyd求最短路

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;//手动定义一个超大数
const int N = 210;
int d[N][N];//d[a][b]表示从a到b的最短距离
int n,m,k;

void floyd(){
    //暴力破解，强行拆中间数，如果过度了一下反而更小了，就更新最短路径
    //这里的顺序也有说法的，中间数第一个，其次是起点最后是终点
  for(int t = 1;t <= n;t++){//注意这里下标要从1开始，因为题目里说了是1~n
    for(int i = 1;i <= n;i++){
      for(int j = 1;j <= n;j++){
        d[i][j] = min(d[i][j] ,d[i][t]+d[t][j]);
      }
    }
  }
}

int main(){
  cin >> n >> m >> k;

  for(int i = 1;i <= n;i++){//初始化距离如果是a到a就是0，如果是ab就是无穷大
    for(int j = 1;j <= n;j++){
      if(i == j) d[i][j] = 0;
      else d[i][j] = INF;
    }
  }

  for(int i = 1;i <= m;i++){//手动更新x到y的距离
    int x,y,z;
    cin >> x >> y >> z;
    d[x][y] = min(d[x][y],z);
  }

  floyd();//进行暴力破解

  for(int i = 1;i <= k;i++){
    int x,y;
    cin >> x >> y;
    if(d[x][y] > INF / 2){//这里是/2是因为有负权边，导致d[x][y]更新了一下，不为INF了，有负权边统一大于无穷大一半就行
      cout << "impossible" << endl;
    }else{
      cout << d[x][y] << endl;
    }
  }
}