算法初探 - 最短路径
更新记录
【1】2020.05.21-00:36
1.完善dijkstra
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
正文
铅制芝士（会一点点就行啦~）
- 动态规划
- 贪心
- 链式前向星
持续更新中...
在学习图论算法的时候，最短路算法就是必学算法之一
那么既然它这么重要，就更需要我们深入了解，熟练掌握
默认图为连通图
dijkstra算法
有点贪心动规的意思
- 我们可以发现，起点到任何一个点的最短路都要经过至少一个的中转点（起点s也算一个中转点）
- 那么我们发现，如果想求出这个点的最短路，那么必定要求出它中转点的最短路
-
- 首先dijkstra算法不能处理负边权，所以我们在使用时默认图无负边权
-
- 所以1-其中一个中转点的最短路，一定小于等于1-终点的最短路
-
- 当小于时，中转点比其先确定最短路
-
- 当等于时，谁先处理都是一样的结果
- 那么依此类推，最后终将推到一个最最最简单的问题：两点间的最短路
这个问题只要你会存图人就会做
（很像动态规划对不对）
^RT，我们要求出1-5的最短路径
就必须求出起点到中转点的最短路径，中转点为4
想求出1-4的最短路径，就先去求1-3的最短路径
同理求1-2
而1-2的最短路就是其连接边的权值
算法思路：
定义变量（链式前向星的那堆变量就不再重复写了）：
dis[i]：表示从起点到i的最短距离
f[i]：记录这条边有没有被确定过最短路
s表示起点
初始化：dis[i]=∞;dis[s]=0
遍历每一个点
- 对于每一个点a，找到一个dis[b]最小的顶点b
- b被确定过最短路
- 遍历所有以b为起点的边，更新它们的dis
算法结束
#include<iostream>
using namespace std;
#define NUM 500050
#define INF 2147483647
struct Edge{
int na,np,w;
}e[NUM];
int head[NUM],dis[NUM],num,n,m,s,u,v,w,minn;
bool f[NUM];
inline void add(int f,int t,int w){
e[++num].na=head[f];
e[num].np=t,e[num].w=w;
head[f]=num;
}
int main(){
cin>>n>>m>>s;
for(int i=0;i<m;i++){
cin>>u>>v>>w;
add(u,v,w);
}
//初始化
for(int i=1;i<=n;i++) dis[i]=INF;
dis[s]=0;
//遍历每一个点
for(int i=1;i<=n;i++){
//对于每一个点a，找到一个dis[b]最小的顶点b
minn=-1;
for(int o=1;o<=n;o++)
if(f[o]==0&&(dis[minn]>dis[o]||minn==-1)) minn=o;
//b被确定过最短路
f[minn]=1;
//遍历所有以b为起点的边，更新它们的dis
for(int o=head[minn];o!=0;o=e[o].na)
if(!f[e[o].np])
dis[e[o].np]=min(dis[e[o].np],dis[minn]+e[o].w);
}
//算法结束，输出s到各点的最短距离
for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
}
更多精彩
