一起学习交流~

图-03-最短路径

算法 laomuji 7个月前 (03-01) 370次浏览 已收录 0个评论

最短路径

在带权图中,从一个点到其它顶点的经过的最小权重就是最短路径
使用以下四种方式求最短路径
folyd,bellmanford,spfa,dijkstra

题目

力扣的743题网络延迟时间
https://leetcode-cn.com/problems/network-delay-time/

folyd

也叫插点法,复杂度最高,n^3
需要使用邻接矩阵的方式
三层循环分为中转点,起点,终点,依次枚举
推荐用于数据量不大的场合

class Solution {
private:
    const int INF = 1e8;//假设正无穷为1e8
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>>edges(n+1,vector<int>(n+1));//编号从1开始,所以+1
        for(int i =1;i<=n;i++){
            for(int j =1;j<=n;j++){
                if(i==j)edges[i][i]=0;
                else edges[i][j]=INF;
            }
        }
        //将数据存入邻接矩阵
        for(const auto& time:times){
            edges[time[0]][time[1]]=time[2];
        }
        //folyd暴力求解
        folyd(edges,n);
        int result = -1;
        for(int i =1;i<=n;i++){
            result = max(result,edges[k][i]);
        }
        return result==INF?-1:result;
    }
    void folyd(vector<vector<int>>&edges,int n){
        for(int i =1;i<=n;i++){//枚举中转点
            for(int j=1;j<=n;j++){//枚举起点
                for(int k=1;k<=n;k++){//枚举终点
                    //判断是直接相连比较近还是经过中转点比较近
                    edges[j][k]=min(edges[j][k],edges[j][i]+edges[i][k]);
                }
            }
        }
    }
};

bellman ford

用数组记录每个点的最短路径,可以不用邻接矩阵
复杂度为 ve (v为点的数量,e为边的数量)
通常为了严格达到v
e的复杂度,使用类存储边并全部放到一个容器里
但该方法并不推荐使用,速度和folyd差不多

class Solution {
private:
    const int INF = 1e8;//假设正无穷为1e8
    struct Edge{
        int u;
        int v;
        int w;
        Edge(int _u,int _v,int _w){
            u=_u;
            v=_v;
            w=_w;
        }
    };
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<Edge>edges;
        for(const auto&time:times){
            edges.push_back(Edge(time[0],time[1],time[2]));
        }
        vector<int>vertexs(n+1,INF);//存放到每个点的最短路径
        vertexs[k]=0;//起点不需要时间
        bellmanford(edges,vertexs,n);
        int result = -1;
        for(int i=1;i<vertexs.size();i++){
            result=max(result,vertexs[i]);
        }
        return result==INF?-1:result;
    }
    void bellmanford(vector<Edge>&edges,vector<int>&vertexs,int n){
        vector<int>lastVertexs;
        for(int i=1;i<=n;i++){//遍历次数
            lastVertexs=vertexs;//复制上次的结果
            for(int j=0;j<edges.size();j++){//遍历边
                int u = edges[j].u;//起点
                int v = edges[j].v;//终点
                int w = edges[j].w;//权值
                //上次u的值+边的权值 = 这条边到v点的值
                //比较是否需要更新最短路径
                vertexs[v]=min(vertexs[v],lastVertexs[u]+w);
            }

        }
    }
};

SPFA

spfa是对bellman ford的优化,一般使用队列,也可以使用栈优化
区别是 只更新了变化了最短距离的点,极大的减少了无用计算
邻接矩阵邻接表都可以 复杂度e*v

class Solution {
private:
    const int INF = 1e8;//假设正无穷为1e8
    struct Edge{
        int v;
        int w;
        Edge(int _v,int _w){
            v=_v;
            w=_w;
        }
    };
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<Edge>>edges(n+1,vector<Edge>());//邻接表
        vector<int>vertexs(n+1,INF);//存放到每个点的最短路径
        for(const auto&time:times){
            edges[time[0]].push_back(Edge{time[1],time[2]});
        }
        spfa(edges,vertexs,n,k);
        int result = -1;
        for(int i=1;i<=n;i++){
            result=max(result,vertexs[i]);
        }
        return result==INF?-1:result;
    }
    void spfa(vector<vector<Edge>>&edges,vector<int>&vertexs,int n,int start){
        vertexs[start]=0;//起点不需要时间
        vector<bool>visit(n+1,false);//已加入队列的数据标记
        visit[start]=true;//起点加入队列标记
        queue<int>que;
        que.push(start);//把起点加入队列
        while(que.size()){
            int u = que.front();que.pop();
            visit[u]=false;//标记为未加入队列
            //寻找u相连的边
            for(int i =0;i<edges[u].size();i++){
                int v = edges[u][i].v;
                int w = edges[u][i].w;
                if(vertexs[v] > vertexs[u]+w){
                    vertexs[v] = vertexs[u]+w;
                    if(visit[v])continue;//如果已经加入队列不需要重复加入
                    que.push(v);//加入队列
                    visit[v]=true;//标记已经加入队列
                }
            }
        }
    }
};

dijkstra

表现稍微比spfa好一点点,复杂度也是e*v
主要是 每次找出一个未被访问的最小的点(防止重复,所以要未被访问)
将其标记为已经访问,并且利用该点所i连接的所有路径
检测由该点出发到达另外一个点是否更近
极端情况下,比如点多边少或者存在重复边的情况下,可以采用优先级队列(小根堆)进行优化

class Solution {
private:
    const int INF = 1e8;//假设正无穷为1e8
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>>edges(n+1,vector<int>(n+1,INF));//邻接矩阵
        vector<int>vertexs(n+1,INF);//存放到每个点的最短路径
        for(const auto&time:times){
            edges[time[0]][time[1]]=time[2];
        }
        dijkstra(edges,vertexs,n,k);
        int result = -1;
        for(int i=1;i<=n;i++){
            result=max(result,vertexs[i]);
        }
        return result==INF?-1:result;
    }
    void dijkstra(vector<vector<int>>&edges,vector<int>&vertexs,int n,int start){
        vector<bool>visit(n+1,false);//是否已经访问过了
        vertexs[start]=0;//起点距离为0
        for(int i =1;i<=n;i++){//需要迭代n次
            int u = -1;
            int minU = INF;
            for(int j = 1;j<=n;j++){//遍历各点
                //找到距离最短且未被更新的节点
                if(visit[j]==false && minU > vertexs[j]){
                    u = j;
                    minU = vertexs[j];
                }
            }
            if(u==-1)break;//若没有未更新的节点了,直接返回
            visit[u] = true;//标记访问
            //通过u去更新其它点
            for(int v =1;v<=n;v++){
                vertexs[v] = min(vertexs[v],vertexs[u]+edges[u][v]);
            }
        }
    }
};
class Solution {
private:
    const int INF = 1e8;//假设正无穷为1e8
    struct Edge{
        int v;
        int w;
        Edge(int _v,int _w){
            v=_v;
            w=_w;
        }
    };
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<Edge>>edges(n+1,vector<Edge>());//邻接表
        vector<int>vertexs(n+1,INF);//存放到每个点的最短路径
        for(const auto&time:times){
            edges[time[0]].push_back(Edge{time[1],time[2]});
        }
        dijkstra(edges,vertexs,n,k);
        int result = -1;
        for(int i=1;i<=n;i++){
            result=max(result,vertexs[i]);
        }
        return result==INF?-1:result;
    }
    void dijkstra(vector<vector<Edge>>&edges,vector<int>&vertexs,int n,int start){
        vector<bool>visit(n+1,false);//是否已经访问过了
        vertexs[start]=0;//起点距离为0
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>que;
        que.push({0,start});
        while(que.size()){
            int u = que.top().second;
            que.pop();
            if(visit[u])continue;
            visit[u]=true;
            //把当前点能通往的点加入队列,小根堆会自动把数据小的放在top上
            //可以解决稀疏表和重边的问题
            for(int i =0;i<edges[u].size();i++){
                int v = edges[u][i].v;
                int w = edges[u][i].w;
                if(vertexs[u]+w < vertexs[v]){
                    vertexs[v] = vertexs[u]+w;
                    que.push({vertexs[v],v});
                }
            }
        }
    }
};

各算法表现

各算法在该题表现如下:

喜欢 (1)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论