声明
无穷大的表示和初始化:
在本文中，用0x3f3f3f3f表示无穷大，0xc0c0c0c0表示无穷小。
对于数组使用cstring 中的 memset函数进行初始化。
#include <cstring>
......
int map[501][501];
memset(map,127,sizeof(map));
//每个数组单元的值为2139062143
优先队列
点及其距离使用pair<距离，点号>保存
并且使用优先队列存储pair
优先队列的定义：
//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
优先队列的API：
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容
优先队列的使用请参考：https://cloud.tencent.com/developer/article/1695851
Dijkstra
Dijkstra算法和图的最小生成树Prim算法非常相似。
给定一个起点，并逐个开始放松。
Prim算法选出当前可达边中权重最小的边。
Dijkstra则是选择当前可达点中距离起点最短的点。
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
int map[501][501];
int dist[501];
int sta[501];
int n,m;
priority_queue<PII, vector<PII>, greater<PII>> pqe;
//本题起点默认为1号点，终点默认为n号点。
int main(){
cin>>n>>m;
memset(map,0x3f,sizeof(map));
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
for(int i=0;i<m;i++){
int x,y,z;
cin>>x>>y>>z;
if(x==y)continue; //处理自环
map[x][y]=min(z,map[x][y]); //处理重边
}
PII start={0,1};
pqe.push(start);//将起点加入队列
//每次将距离起点最近的点松弛，并且将可达点加入队列
while(!pqe.empty()){
PII node=pqe.top();
pqe.pop(); //弹出最小距离点作为当前点point
int point=node.second;
if(sta[point]==1)continue;
sta[point]=1;
for(int i=1;i<=n;i++){ //逐个松弛point的可达点i，并且加入优先队列
if(map[point][i]<dist[i]&&sta[i]==0){//权重不为无穷大（可达点）中未被访问过的
dist[i]=min(dist[point]+map[point][i],dist[i]);
PII newnode ={dist[i],i};
pqe.push(newnode);
}
}
}
if(dist[n]!=0x3f3f3f3f){
cout<<dist[n]<<endl;
return 0;
}
cout<<"-1"<<endl;
}
不使用优先队列版本
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N],dist[N];//用邻接矩阵g[N][N]存储图，dist[N]存储每个点到起点的最小距离
bool st[N];
int n,m;//有n个点，m条边
int Dijkstra(){
memset(dist,0x3f,sizeof dist);//将Dijkstra()数组初始化为无穷大
dist[1]=0;//起点到自身的距离为0
for(int i=0;i<n;i++){//i为生成Dijkstra()数组需要迭代的次数
int t=-1; //设t为本次循环需要迭代的点，下面寻找t点
//t点需要满足两个条件，处于未被确定的状态和在所有未确定的点中，距离起点最近
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
}//这个for循环确定了需要上述t点
st[t]=true;
for(int j=1;j<=n;j++)dist[j]=min(dist[j],dist[t]+g[t][j]);
//基于t点进行迭代，对每个点j，取"起点->t->j"||"起点->j"的小值
}
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];//事实上生成了每个点到起点的最小距离，修改此处可查
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g);//初始化邻接矩阵为O
while(m--){
int x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z);//将x到y的距离存储为最小的（可能有重边）
}
cout<<Dijkstra()<<endl;
return 0;
}
大数据量版 (n最大达到了1e5,开不出这么大的二维数组)
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}
拓扑排序松弛法
Bellman-ford（k步法）
有负环的图能不能搞出最短路？将所有边的权重加上最小负值的绝对值行不行？
答案是不行！，这样做将图的实际意义作出了曲解 。
负环只能用bellman-ford检测，不一定有最短路。路径上有负环不存在最短路径了。
spfa找负权环