最短路径
Dijkstra算法
求单源最短路
P4779 【模板】单源最短路径（标准版）
邻接矩阵版本：
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1005;
const int INF=0x3f3f3f3f;
int g[maxn][maxn],dist[maxn];
// g[][]为邻接矩阵，dist[i]表示源点到节点i的最短路长度
int p[maxn];// p[i]表示源点到节点i的最短路径上i的前驱
bool f[maxn];// 如果f[i]等于1，说明节点i已加入s集合；否则i属于V-S集合
int n,m,s,u,v,w;
void dijkstra(int u){// u为源点
for(int i=1;i<=n;i++){// 初始化
dist[i]=g[u][i];
f[i]=0;
if(dist[i]==INF){// 节点i与u不相邻
p[i]=-1;
}else{// 节点i与u相邻，设置节点i的前驱p[i]=u
p[i]=u;
}
}
dist[u]=0;
f[u]=1;// u加入s集合
for(int i=1;i<n;i++){// 重复n-1次
int sum=INF,t=u;
for(int j=1;j<=n;j++){// 找V-S集合中dist[]最小
if(f[j]==0&&dist[j]<sum){
sum=dist[j];
t=j;
}
}
if(t==u)return ;// 找不到最短路，无法到达
f[t]=1;
for(int j=1;j<=n;j++){// 判断V-S集合中的节点是否可以借助t更新dist[],松弛操作
if(f[j]==0&&dist[j]>dist[t]+g[t][j]){
dist[j]=dist[t]+g[t][j];// 更新最短距离
p[j]=t;// 记录前驱
}
}
}
}// O(n^2)
void findpath(int u){// 找源点到u的最短路径
if(u==-1)return ;
findpath(p[u]);
cout<<u<<" ";
}
int main(){
cin>>n>>m>>s;
memset(g,0x3f3f3f3f,sizeof(g));
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
g[u][v]=w;
}
dijkstra(1);
for(int i=1;i<=n;i++){
cout<<dist[i]<<" ";
}
return 0;
}
邻接表+优先队列优化版本：
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int n,m,s;
int u,v,w;
struct edges{
int to;
int next;
int dist;
};
vector<edges> edge;
int head[maxn];
int edgenum;
void add(int u,int v,int w){
edge.push_back((edges){v,head[u],w});
head[u]=edgenum++;
}
int dist[maxn],p[maxn];
bool f[maxn];
struct node{
int dist;
// 表示从起始点到当前顶点的距离（或者说最短路径的长度）
int p;
// 表示当前顶点的编号或标识
bool operator <(const node &x) const{
// 定义了一个 operator< 重载函数
// 这个函数用来定义结构体node之间的比较操作，主要用于优先队列q中的元素排序
return x.dist<dist;
// 通过比较x.dist和dist的大小，从而决定哪个结构体node应该排在前面
}
};
priority_queue<node> q;
// 优先队列，用于按照最小距离维护待处理的顶点集合
void dijkstra(int u){
dist[u]=0;
// 从起始点到自身的距离为0
q.push((node){0,u});
// 将起始点u添加到优先队列q中
while(!q.empty()){
// 只要优先队列q不为空，就继续循环
node sum=q.top();
q.pop();
// 每次循环从队列中取出距离最短的顶点x，它的距离是dist[x]
int x=sum.p;
if(f[x]==1){
// 检查顶点x是否已经被访问过
continue;
// x已经被访问过，就跳过这个顶点，继续下一轮循环
}
f[x]=1;
// 将顶点x标记为已经访问过
for(int i=head[x];i!=-1;i=edge[i].next){
// 这是一个循环，遍历顶点x的所有邻接边
int v=edge[i].to;
// 取得当前邻接边的终点顶点v
if(dist[v]>dist[x]+edge[i].dist){
// 检查从起始点 u 经过顶点x到达顶点y的路径是否比当前记录的最短路径还短
dist[v]=dist[x]+edge[i].dist;
// 如果是，就更新dist[v]为更短的路径长度
if(f[v]==0){
// 确保在将新的顶点加入优先队列时，只加入尚未被访问过的顶点
q.push((node){dist[v],v});
// 并将(node){dist[v],v}加入队列q中，以便进一步探索以v为起点的路径
}
}
}
}
}
void findpath(int u){// 查找最短路径
if(u==-1)return ;
findpath(p[u]);
cout<<u<<" ";
}
int main(){
cin>>n>>m>>s;
memset(head,-1,sizeof(head));
memset(dist,0x3f3f3f3f,sizeof(dist));
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
dijkstra(s);
for(int i=1;i<=n;i++){
cout<<dist[i]<<" ";
}
return 0;
}// P4779
floyed
各个顶点间最短路
Bellman-Ford
单源最短路，可解决负权边的问题
也可以判负环
SPFA
单源最短路径
其实就是队列优化后的Bellman-Ford