前言

乍一看搜索跟这个一样都可以找出一个点到另一个点的最短距离，但是有些问题两者都可以解决，而另一些搜索就不能解决了，搜索有确定的方向一步一步走，而最短路是告诉你某两个点直接可以直接走，没有确定的方向。最短路问题，通俗的说就是就是给你n个点，m条边，然后找出某两个点之间的最短距离。解决最短路常用的有三种算法Floyd、Dijkstra、SPFA。三种方法各有优劣

  1. Floyd算法是多源最短路算法，复杂度最高（n^3），通常用在点比较少的起点不固定的问题中。能解决负边（负权）但不能解决负环。
  2. Dijkstra算法是单源最短路算法，最常用时间复杂度（n^2）优化后可以达到（nlogn），不能解决负边问题，稀疏图（点的范围很大但是边不多，边的条数|E|远小于|V|²）需要耗费比较多的空间。
  3. SPFA算法适合稀疏图，可以解决带有负权边，负环的问题，但是在稠密图中效率比Dijkstra要低。

Floyd算法

Floyd算法比较简单，就是暴力枚举了所有的可能，将所有可能找遍就知道了两点之间的最短路

参数解释

  1. Chara数组 ：储存两点间的距离，Chara[i][j]的值就是点i到点j的距离。
  2. n：总共有n个点。
  3. p[i][j]:代表对应顶点的最小路径的前驱矩阵
  4. MAX：定义最大值，路不通的情况距离就是MAX

算法思想

很容易理解，我们从一个点i到另一个点j,无非就两种走法

  1. 直接从i到j
  2. 通过中间点k中转，i->k->j

所以我们就遍历所有情况，如果通过某个中转点距离小于直接到达的距离，就更新这两点间的距离。 

if(Chara[i][j] > Chara[i][k] + Chara[k][j])
    Chara[i][j] = Chara[i][k] + Chara[k][j];

代码

#define MAX 65535
int Chara[N][N], p[N][N];
int n, m;
void Floyd() {
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            p[i][j]=j;//初始化
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(Chara[i][k] == MAX || Chara[k][j] == MAX)
                    continue;
                if(Chara[i][j] > Chara[i][k] + Chara[k][j]) {
                    //如果经过下标k顶点路径比原两点间路径更短
                    //将当前两点权值设为更小的那一个
                    Chara[i][j] = Chara[i][k] + Chara[k][j];
                    p[i][j] = p[i][k];//路径设置经过下标k的顶点
                }
            }
        }
    }
}



Dijkstra算法

Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

参数解释

  1. Chara数组 ：储存两点间的距离，Chara[i][j]的值就是点i到点j的距离。
  2. dis数组：储存起点到各个点的距离，dis[i]就是起点到i点的距离。
  3. vis数组：标记点是否访问过
  4. INF：宏定义的最大值路不通

算法思想

有两个数组，dis和vis含义参见上面，初始时vis中只有起点，更新dis中的起点到所有点的距离
遍历所有节点，找到距离起点最近的一个点K，将这个点加入vis中标记
进行松弛操作，遍历没有在vis数组中的其他所有点，比较起点->该点和起点->K点->该点的距离，
重复2-3操作，直到所有的点遍历完

代码

#define INF 65535
int n, m, s, t;
int Chara[N][N], dis[N], vis[N], p[i];
void Dijkstra(int src) { //src传入的起点
    for(int i = 0; i < m; i++) { //初始化起点到所有点的距离
        dis[i] = Chara[src][i];
        vis[i] = 0;
        p[i]=0;
    }
    dis[src] = 0; //到自身距离为0
    vis[src] = 1; //标记 注src=0
    for(int i = 0; i < m; i++) {
        int ans = INF, k;
        for(int j = 0; j < m; j++) { // 寻找未被访问过距离起点v0最近的
            if(!vis[j] && dis[j] < ans) {
                k = j;
                ans = dis[j];
            }
        }
        vis[k] = 1;   //标记已访问
        if(ans == INF) break; //表示剩下所有点都不通
        for(int j = 0; j < m; j++) { 
        //松弛操作，更新起点到所有未访问点的距离
            if(!vis[j] &&  dis[k] + Chara[k][j] < dis[j] ) {
                dis[j] = dis[k] + Chara[k][j];
                p[j]=k;//存放前驱节点
            }
        }
    }
}

前向星版

int dij(int u) {
    dis[u] = 0;
    while(true) {
        int k = -1;
        int min = INF;
        for(int i = 0; i < n; i++) {
            if(!vis[i] && dis[i] < min) {
                min = dis[i];
                k = i;
            }
        }
        if(k == -1) break;
        vis[k] = true;
        for(int i = head[k]; ~i; i = edge[i].nxt) {
            if(!vis[edge[i].v] && dis[k] + edge[i].w < dis[edge[i].v]) {
                dis[edge[i].v] = dis[k] + edge[i].w;
            }
        }
    }
}

SPFA算法

SPFA是一种用队列优化的B-F算法，看上去和BFS很像，B-F效率较低就不介绍了，还有一种用DFS优化B-F的SPFA但是往往这种方法比平时更加劣化没有队列优化的好用，平时用SPFA就够用了。可以解决负边问题，可以判断负环是否存在。在稀疏图中，采用类似邻接链表储存比较节省空间。

参数解释

  1. node结构体：用来储存边，数组下标代表边起点，结构体中的v，代表边的终点，weight/w代表权值
  2. dis数组：储存起点到各个点的距离，dis[i]就是起点到i点的距离。
  3. vis数组：标记点是否访问过
  4. INF：宏定义的最大值路不通

算法思想

  1. 初始时，只有把起点放入队列中。
  2. 遍历与起点相连的边，如果可以松弛就更新距离dis[],然后判断如果这个点没有在队列中就入队标记。
  3. 出队队首，取消标记，循环2-3步，直至队为空。
  4. 所有能更新的点都更新完毕，dis[]数组中的距离就是，起点到其他点的最短距离。

为什么SPFA可以处理负边：因为在SPFA中每一个点松弛过后说明这个点距离更近了，所以有可能通过这个点会再次优化其他点，所以将这个点入队再判断一次，而Dijkstra中是贪心的策略，每个点选择之后就不再更新，如果碰到了负边的存在就会破坏这个贪心的策略就无法处理了。 如何判断成环： 在储存边时，记录下每个点的入度，每个点入队的时候记录一次，如果入队的次数大于这个点的入度，说明从某一条路进入了两次，即该点处成环。

代码

const int INF = 0x3f3f3f3f;
const int N = 210;
int n, m, s, t;
int dis[N], vis[N], sum[N];
struct node {
    int v; //点
    int weight; //权值
};
vector<node> mp[N]; //储存边;
//SPFA写法
void SPFA(int src) {
    int q;
    queue<int> Q;
    vis[src] = 1;
    dis[src] = 0;
    Q.push(src);
    while(!Q.empty()) {
        q = Q.front();
        Q.pop();
        vis[q] = 0;
        for(int i = 0; i < mp[q].size(); i++) {
            if(dis[q] + mp[q][i].weight < dis[mp[q][i].v]) {
                dis[mp[q][i].v] = dis[q] + mp[q][i].weight;
                if(!vis[mp[q][i].v]) {
                    Q.push(mp[q][i].v);
                    vis[mp[q][i].v] = 1;
                }
            }
        }
    }
    return;
}

模板 转自

发表回复