最短路径算法（Bellman-Ford/Dijkstra/Floyd）

女爷i 2022-12-28 07:29 359阅读 0赞

### 文章目录 ###

*  最短路径算法
 *   *  Bellman-Ford（单源最短）
     *   *  算法核心
         *   *  负环的判断
         *  算法代码
         *  算法分析
     *  Dijkstra算法（单源）
     *   *  算法核心
         *   *  无法判断存在负权边的图
         *  算法代码
         *  算法分析
     *  堆优化的Dijkstra算法（单源）
     *   *  算法核心
         *  算法代码
     *  Floyd算法（多源）
     *   *  算法核心
         *   *  可判断负环
         *  算法代码
         *  算法分析

--------------------

# 最短路径算法 #

最短路径算法

## Bellman-Ford（单源最短） ##

### 算法核心 ###

*  对于每一个边都看能不能去更新单源最短路径
 *  在更新过程中并不确定哪一个边就是最短路径，而是始终抱着试探的心态去更新最短路径
 *  一旦某一次起点到其他结点的最短路径不更新时，就表示全部为最短路径

#### 负环的判断 ####

> **Bellman-Ford算法可以判断图中是否有负环，当出现负环时是不存在最短路的，并且易知最多通过(V-1)条路就能到达任何一个点并且距离最短，因此如果在第V次的循环仍能更新最短路径表，则代表图中存在负环**

### 算法代码 ###

const int MAX_E=10000;
    const int MAX_V=10000;
    const int INF=99999;
    
    struct edge
    {
        
        int from,to,cost;
    }es[MAX_E]; //记录边的数组
    
    int dist[MAX_V];    //最短路径表
    int V,E;    //顶点数和边数
    
    //从起点s出发到其它点的最短路径，true表示有负环，false表示无负环
    bool bellman_ford(int s)
    {
        
        for(int i=0;i<V;i++) dist[i]=INF;
        
        dist[s]=0;  //s->s的最短距离为0
        while(true){
        
            bool update=false;
            
            for(int i=0;i<E;i++){
        
                edge e=es[i];
                if(dist[e.from]<dist[e.to]+e.cost){
         //对每个边都看，是否能够通过这个边以更小的代价到达某个点
                    dist[e.from]=dist[e.to]+e.cost;
                    update=true;
                }
            }
            
            if(!update) break;  //一旦有一次不再更新，就求解出来最短路径了
        }
        
        bool fuhuan=false;
        for(int i=0;i<E;i++){
        
            edge e=es[i];
            if(dist[e.from]<dist[e.to]+e.cost){
         //对每个边都看，是否能够通过这个边以更小的代价到达某个点
                dist[e.from]=dist[e.to]+e.cost;
                fuhuan=true;
            }
        }
        
        return fuhuan;
    }

### 算法分析 ###

> **算法的时间复杂度为O(|V|\*|E|)**

## Dijkstra算法（单源） ##

### 算法核心 ###

*  在最短路径表中每次确定一个不可改变的最短路径，以此为基准依次更新最短路径表

#### 无法判断存在负权边的图 ####

因为每次都确定了一个不可改变的最短路径，因此存在一定的局部片面性

例如：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

最后结果的最短路径表：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]

实际的最短路径表：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]

### 算法代码 ###

const int MAX_V=10000;
    const int INF=99999;
    
    int cost[MAX_V][MAX_V]; //cost[u][v]表示边e=(u,v)的权值，不存在时设置为INF
    int dist[MAX_V];   //顶点s出发的最短距离
    bool used[MAX_V];   //已经使用过的点
    int V;  //顶点数
    
    void dijkstra(int s)
    {
        
        fill(dist,dist+V,INF);
        fill(used,used+V,false);
        dist[s]=0;
        
        while(true){
        
            int v=-1;
            for(int i=0;i<V;i++){
        
                if(!used[i]&&(v==-1||dist[i]<dist[v])) v=i;
            }
            
            if(v==-1) break;
            used[v]=true;
            
            for(int i=0;i<V;i++)
                dist[i]=min(dist[i],dist[v]+cost[v][i]);
        }
    }

### 算法分析 ###

> **算法的复杂度为O(|V|2)**

## 堆优化的Dijkstra算法（单源） ##

### 算法核心 ###

*  每次都将更新过的边的最短路径和顶点编号压入最小堆中，直到堆为空

### 算法代码 ###

const int INF=99999;
    const int MAX_V=100000;
    struct edge
    {
        
        int to,cost;
    };
    
    typedef pair<int , int> P;  //first是最短距离，second是顶点的编号
    
    int V;  //顶点数
    vector<edge> G[MAX_V];  //邻接表存储
    int dist[MAX_V];    //最短路径表
    
    void dijkstra(int s)
    {
        
        //最小堆
        priority_queue<P,vector<P>,greater<P>> que;
        
        fill(dist,dist+V,INF);
        dist[s]=0;  //s到s的最短距离为0
        que.push(P(0,s));   //将s到s的最短距离压入堆中
        
        while(!que.empty()){
        
            P p=que.top(); que.pop();
            int v=p.second; //v为该最短路的结点
            if(dist[v]<p.first) continue;   //若最短路表中记录的最短路与弹出小，则证明到该结点的最短路是旧纪录
            //遍历结点v的邻接表，更新相邻结点的最短路径
            for(int i=0;i<G[v].size();i++){
        
                edge e=G[v][i];
                if(dist[e.to]>dist[v]+e.cost){
        
                    dist[e.to]=dist[v]+e.cost;
                    que.push(P(dist[e.to],e.to));
                }
            }
        }
    }

## Floyd算法（多源） ##

### 算法核心 ###

*  任意两个点的最短路径，都认为能够通过某个中间点进行中转之后达到最短路径

#### 可判断负环 ####

*  当某个结点到自身的距离为负数时，即存在负环

### 算法代码 ###

const int MAX_V=100000;
    int d[MAX_V][MAX_V];    //邻接矩阵，在最终为多源最短路径表
    int V;  //顶点数
    
    void floyd()
    {
        
        for(int k=0;k<V;k++)
            for(int i=0;i<V;i++)
                for(int j=0;j<V;j++)
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    }

### 算法分析 ###

> **算法的时间复杂度为O(|V|3)**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/d74aef9b6ed94123b27b1ec242ae5888.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201215145237942.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201215145243470.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70