首先讲解一下链式前向星是什么. 简单的来说就是用一个数组 (用结构体来表示多个量) 来存一张图, 每一条边的出结点的编号都指向这条边同一出结点的另一个编号(怎么这么的绕)
如下面的程序就是存链式前向星.(不用链式前向星用邻接矩阵过不了, 因为数据大会超空间限制)
- struct node{
- int quan,to,qian;
- }lian[500010];
- int qian[10010];// 开始都为 0, 是个边界
- void add(int x,int y,int z){
- lian[++ans].qian=qian[x];// 存前一个的编号, 自己可以模拟一下很好理解的
- lian[ans].quan=z;// 存对应的比边权
- lian[ans].to=y;// 与之相连的点是哪一个存下来
- qian[x]=ans;// 变成当前编号方便存下一个
- }
学会了链式前向星, 接下来就是 Dijkstra 算法.
Dijkstra 算法是基于贪心的算法, 它是寻找每一点相连的边的最小值, 在对整个图进行更新, 做 n-1 次, 也可以认为是一种动态规划, 但不适用于有负边的情况, 以后我会对它进行堆优化, 现在用的 Dijkstra 是未经优化的版本.
在很多高级算法的书上都会提到, 我就不画图和证明正确性了, 借助程序讲
- #include<bits/stdc++.h>
- using namespace std;
- struct node{
- int quan,to,qian;
- }lian[500010];
- int n,m,s,dis[10010],ans,qian[10010];
- bool vis[10010];
- void add(int x,int y,int z){
- lian[++ans].qian=qian[x];
- lian[ans].quan=z;
- lian[ans].to=y;
- qian[x]=ans;
- }// 链式前向星存储
- void dijkstra(){
- memset(vis,false,sizeof(vis));
- memset(dis,0x3f,sizeof(dis));
- dis[s]=0;
- int now=s;
- vis[s]=true20 for (int i=1;i<n;i++){// 要将整张图寻找, 所以要找 n-1 次
- vis[now]=true;// 记录是否已经遍历过
- int p=qian[now];
- while (p!=0){// 边界是 0 前面已经说明, 要自己理解
- if (not vis[lian[p].to]&&(lian[p].quan+dis[now]<dis[lian[p].to]))
- dis[lian[p].to]=lian[p].quan+dis[now];
- p=lian[p].qian;
- } // 链式前向星寻找, 每次更新没有遍历过的点的最小值
- int minn=0x7fffffff;
- for (int j=1;j<=n;j++)
- if (not vis[j]&&dis[j]<minn){
- minn=dis[j];
- now=j;// 找最小的没遍历的点继续更新
- }
- }
- }
- int main(){
- scanf("%d%d%d",&n,&m,&s);
- for (int i=1;i<=m;i++){
- int a,b,c;
- scanf("%d%d%d",&a,&b,&c);
- add(a,b,c);// 处理读入数据
- }
- dijkstra();
- for (int i=1;i<=n;i++){
- if (dis[i]>100000000) printf("%d",2147483647);
- else printf("%d",dis[i]);// 输出结果
- }
- }
来源: https://www.cnblogs.com/fnbk/p/9321115.html