无向带权图求两个节点之间的最短路径（C++）

59 阅读 0 评论 39 点赞

我是靠谱客的博主爱笑乌冬面，最近开发中收集的这篇文章主要介绍无向带权图求两个节点之间的最短路径（C++），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

在这里插入图片描述
输入
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

收获

1：大概应该好像学会了dijkstra算法，首先依据给的节点之间的关系建立双向映射，然后依次从起点起开始遍历，每个节点只能遍历1次，找到依据当前节点从初始位置到达下一位置是否会变小，如果变小了则说明路径较好，入队列，同时最小堆的好处可以使得对于每一个元素，取到的都是最小值更新好的避免了很多次的重复比较

代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N=100005;
typedef pair<int,int>pii;
vector<pii>graph[N];
//这里的graph定义怀疑了自己好久才明白！！！，原来自己以往定义的（n,0）的形式都是直接定义n那么大的数组，定义双重数组自己往往
//vector<vector<int ,int>>这种形式，其实可以直接vevtor<int>res[n]就像定义数组一样，每一个元素都是vector类型！！真的是受益良多！
priority_queue<pii,vector<pii>,greater<pii>>pq;
vector<bool>flag(N,0);
vector<int >mind(N,127);

int shortestPath(int n,int m,vector<int >U,vector<int >V,vector<int >W,int s,int t){
    for(int i=0;i<m;i++){
        //这里也觉得有丢丢问题~
        graph[U[i]].push_back(make_pair(V[i],W[i]));
        graph[V[i]].push_back(make_pair(U[i],W[i]));
    }
    mind[s]=0;
    pq.push(make_pair(mind[s],s));
    while(!pq.empty()){
        int u=pq.top().second;
        pq.pop();
        //每个节点最多一次？why？
        //maybe I know!
        if(!flag[u]){
            flag[u]=1;
            //在这次编程中学到的知识有，auto的使用，可以像下面这样写，其中的it获得到的是对应元素指向的首地址，所以在下文访问
            //的时候需要用->这个箭头访问内部元素，但是如果想要使用auto&it这种方式的话，已经取完址到达对应的位置了，
            //再次访问时，只需要使用.方法访问内部元素即可，参考链接https://blog.csdn.net/qq_41867145/article/details/115067887
            for(auto it=graph[u].begin();it!=graph[u].end();it++){
                int v=it->first,w=it->second;
                if(flag[v]||mind[v]<mind[u]+w)
                    continue;
                mind[v]=mind[u]+w;//进行更新
                pq.push(make_pair(mind[v],v));
            }
        }
    }
    return mind[t];
}

int main()
{
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    vector<int >U,V,W;
    U.clear();
    V.clear();
    W.clear();
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        U.push_back(u);
        V.push_back(v);
        W.push_back(w);
    }
    cout <<shortestPath(n,m,U,V,W,s,t)<< endl;
    return 0;
}