算法十三：最短路

绝地灬酷狼 2022-05-23 20:07 133阅读 0赞

问题描述

给定一张 n 个点的无向带权图，节点的编号从 1 至 n，求从 S 到 T 的最短路径长度。

### 输入格式 ###

第一行 4 个数 n,m,S, T，分别表示点数、边数、起点、终点。

接下来 m 行，每行 3 个正整数 u,v,w，描述一条 u 到 v 的双向边，边权为 w。

保证 1<=u,v<=n。

### 输出格式 ###

输出一行一个整数，表示 S 到 T 的最短路。

### 样例输入 ###

7 11 5 4 （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

### 样例图解 ###

![70][]

###     ###

### 样例输出 ###

7（3+1+3）

### 数据范围 ###

本题共设置 12 个测试点。

对于前 10 个测试点，保证 n<=2500，m<=6200，对于每条边有 w<=1000。这部分数据有梯度。

对于所有的 12 个测试点，保证 n<=100,000，m<=250,000。

### 提示 ###

\[本题是 Dijkstra 算法的模板练习题。\]

\[使用朴素的 Dijkstra 算法可以通过前 10 个测试点。\]

\[使用堆或\_\_std::priority\_queue\_\_优化的 Dijkstra 算法可以通过所有测试点。\]

### 一. 伪代码 ###

![70 1][]

![70 2][]

### 二. 具体实现（C++） ###

\#include <bits/stdc++.h>  
using namespace std;  
// ================= 代码实现开始 =================  
const int N = 100005;  
typedef pair<int,int> pii;  
//graph:存放图，graph\[i\]表示的是节点i的出边，其中first存储到达的节点，second存储边权  
//pq：辅助Dijkstra算法的优先队列  
//flag：记录每个节点是否进行过松弛，1表示进行过，0表示未进行过  
//mind：存储起点s到每个节点的最短路径长度  
vector<pii> graph\[N\];  
priority\_queue<pii,vector<pii>,greater<pii>> pq;  
bool flag\[N\];  
int mind\[N\];  
// 这个函数用于计算答案（最短路）  
// n：节点数目  
// m：双向边数目  
// U,V,W：分别存放各边的两端点、边权  
// s,t：分别表示起点、重点  
// 返回值：答案（即从 s 到 t 的最短路径长度）  
int shortestPath(int n, int m, vector<int> U, vector<int> V, vector<int> W, int s, int t) \{  
while(!pq.empty())  
pq.pop();  
for(int i=1; i<=n; ++i)  
graph\[i\].clear();  
memset(mind,127,sizeof(mind));  
memset(flag,0,sizeof(flag));  
 //建图，连接图中各边  
 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\]));  
\}  
 //设置起点的最短路为0，并将起点加入到优先队列中  
 mind\[s\] = 0;  
pq.push(make\_pair(mind\[s\],s));  
 //执行Dijkstra算法  
 while(!flag\[t\])\{  
int u = pq.top().second;  
pq.pop();  
if(!flag\[u\])\{ //每个节点最多做一次松弛  
 flag\[u\] = 1;  
for(vector<pii>::iterator it = graph\[u\].begin(); it != graph\[u\].end(); ++it)\{ //枚举所有u出发的边  
 int v = it->first, w = it->second;  
if(mind\[v\] <= mind\[u\]+w)  
continue;  
mind\[v\] = mind\[u\] + w;  
pq.push(make\_pair(mind\[v\],v));//将v伴随其最新的最短路径长度加入优先队列  
 \}  
\}  
\}  
 return mind\[t\];  
\}  
// ================= 代码实现结束 =================

[70]: /images/20220524/3f7e79f736cf440faadff30bb53cc24e.png
[70 1]: /images/20220524/826bec749ba24e65b2e6af231dcf7d49.png
[70 2]: /images/20220524/3fd9b9c04fff49289b2ddd653ed52be3.png