最短路
Dijkstra
Dijkstra算法是一种局部贪心策略，用于解决带权有向图的单源最短路，其基本要求是权值中不存在负数。
实现
朴素dijkstra依赖邻接矩阵实现，通过dist和pre数组分别记录点到源点的最短距离、每个点的前驱节点。 由于邻接表在稀疏图存储空间上表现不佳，也为了优化查点效率，可以使用小根堆存储当前距离源点最近点。c++中，通常使用有自定义比较的优先队列来实现。
总体步骤如下：
- 初始化。
初始化dist数组为极大值INF，表示源点到节点i的最小距离；
初始化pre数组为-1，值表示在最短路中节点i的前一个节点；
向优先队列中压入起点，通常是节点1。
-
遍历
-
查优先队列中的最近点并弹出，如果已访问或总距离比dist中记录的最小距离小，跳过，否则标记访问；
-
检查当前最近点能直接到达的所有点，更新dist和pre数组
-
输出结果
模板题
朴素最短路
题目链接：47. 参加科学大会（第六期模拟笔试）
点击展开题目
# 题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。
小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。
小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。
# 输入描述
第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。
接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。
# 输出描述
输出一个整数，代表小明从起点到终点所花费的最小时间。
# 输入示例
# 输出示例
# 提示信息
能够到达的情况：
如下图所示，起始车站为 1 号车站，终点车站为 7 号车站，绿色路线为最短的路线，路线总长度为 12，则输出 12。
不能到达的情况：
如下图所示，当从起始车站不能到达终点车站时，则输出 -1。
数据范围：
1 <= N <= 500; 1 <= M <= 5000;
实现代码
点击展开代码
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct compare{
bool operator()(pair<int,int> a,pair<int,int> b){
return a.second>b.second;
}
};
const int INF=0x3f3f3f3f;
const int MAX=505;
int n,m,a,b,w;
int dist[MAX];
bool flag[MAX];
int pre[MAX]; //前驱节点
vector<pair<int,int>> map[MAX]; //指向节点，花费
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq; //指向节点，花费
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a>>b>>w;
map[a].push_back({b,w});
}
//初始化
for(int i=1;i<=n;i++){
pre[i]=-1;
dist[i]=INF;
}
dist[1]=0;
pq.push({1,0});
//dijkstra
int minCost=INF,minPoint=-1;
while(!pq.empty()){
//查最近点
pair<int,int> currPoint=pq.top();
pq.pop();
minCost=currPoint.second;
minPoint=currPoint.first;
if(dist[minPoint]<minCost)continue;
if(flag[minPoint])continue;
flag[minPoint]=true;
//更新最近点可达点和源点的距离
for(auto point:map[minPoint]){
if(!flag[point.first]&&minCost+point.second<dist[point.first]){
pq.push({point.first,minCost+point.second});
dist[point.first]=minCost+point.second;
pre[point.first]=minPoint;
}
}
}
if(dist[n]==INF)cout<<-1;
else cout<<dist[n];
return 0;
}
小根堆
题目链接：743. 网络延迟时间 - 力扣（LeetCode）
思路
和上一个模板不同，该题要求访问所有点，并找出其中最大的值。 为了访问所有节点，可以在初始化后将所有节点都放进优先队列，直到清空队列才退出处理。
实现代码
点击展开代码
#include <queue>
#include <vector>
class Solution {
public:
const int MAX = 105;
const int INF = 2147483647;
vector<pair<int, int>> graph[105]; // target,dist
int dist[105], pre[105];
bool flag[105];
struct compare {
bool operator()(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, compare>
pq; // target,dist
// 表，点数，起点
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
// 建图
for (auto t : times) {
graph[t[0]].push_back({t[1], t[2]});
}
// 初始化
for (int i = 1; i <= n; i++) {
dist[i] = INF;
pre[i] = -1;
}
dist[k] = 0;
for (auto point : graph[k])
dist[point.first] = point.second;
for (int i = 1; i <= n; i++)
pq.push({i, dist[i]});
// dijkstra
while (!pq.empty()) {
pair<int, int> curr = pq.top();
pq.pop();
//边界检查
//如果当前节点已访问，跳过
if (flag[curr.first])
continue;
//如果当前节点的距离为INF，则该节点距离没有更新过，跳过
if (curr.second == INF)
continue;
//如果已记录的距离小于当前读到的距离，则当前不是一个有效节点，跳过
if (dist[curr.first] < curr.second)
continue;
flag[curr.first] = true;
for (auto point : graph[curr.first]) {
if (flag[point.first])
continue;
//更新距离、前驱节点和优先队列
if (curr.second + point.second < dist[point.first]) {
dist[point.first] = curr.second + point.second;
pre[point.first] = curr.first;
pq.push({point.first, dist[point.first]});
}
}
}
int res = -1;
for (int i = 1; i <= n; i++) {
if (dist[i] == INF)
return -1;
else
res = res > dist[i] ? res : dist[i];
}
return res;
}
};