前言

乍一看搜索跟这个一样都可以找出一个点到另一个点的最短距离,但是有些问题两者都可以解决,而另一些搜索就不能解决了,搜索有确定的方向一步一步走,而最短路是告诉你某两个点直接可以直接走,没有确定的方向。最短路问题,通俗的说就是就是给你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;
}

模板 转自

发表回复