单源最短路径(Dijkstra&Bellman-Ford)

1.Dijkstra算法（基于贪心思想） 步骤： First：初始化dist[1]=0，其余节点的dist值为正无穷大。（dist数组是源点到其他节点的最短距离，这里选定1为源点） Second：找出一个未被标记的且dist[node]最小的节点node，然后标记node。 Third：扫描节点node的所有出边node->ver，边长为z，若dist[ver]>dist[node]+z，则用dist[node]+z更新dist[ver]. Lastly：重复Second，Third两个步骤（emmm）直到所有节点被标记。 然后。。。没有然后了，上代码：

#include<iostream> #include<cstdio> #include<cmath> #include<cstring>//memset函数需要用到 using namespace std; int a[1005][1005],dist[1005];//a[][]用来存边,dist[]用来存源点到其他点的最短距离 int n,m; bool vis[1005];//标记数组 ～ 路过 void dijkstra() { memset(dist,0x3f,sizeof(dist));//没有开始时，除了源点到源点的距离是0外，你还知道啥 emmm memset(vis,false,sizeof(vis)); //这句可以不加，定义完之后默认全是false dist[1]=0; for(int i=1;i<n;i++)//只需进行n-1次 emmm { int m=0;//16～18行 找dist数组中未被标记的最小的点 for(int j=1;j<=n;j++) if(!vis[j]&&(m==0||dist[j]<dist[m])) m=j; vis[m]=true;//找到了就把它标记上 for(int k=1;k<=n;k++) //20～21行 看你找到的点所有出边能否更新dist数组 dist[k]=min(dist[k],dist[m]+a[m][k]); } } int main() { scanf("%d%d",&n,&m);//n个点,m条边 memset(a,0x3f,sizeof(a));//数组初始化,也可以用for循环,我比较懒emmm。void函数里的这个东西同理 for(int i=1;i<=n;i++) a[i][i]=0;//自己到自己的距离当然是0啦～ for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[x][y]=z;// 这里是有向图，无限图的话加一句a[y][x] =z; } dijkstra(); for(int i=2;i<=n;i++) printf("%d ",dist[i]); return 0; }

这里我们用的邻接矩阵存图，比较好懂。（还是我懒，emmm） 但是存图的话我们经常用到邻接表。那么邻接表是个啥子东西呢，这里附上临界表的核心代码：

void add(int x,int y,int z)//x,y是点 z是这连接这两个点的边的长度 { ver[++tot]=y; edge[tot]=z; net[tot]=head[x]; head[x]=tot; }

其中ver数组代表这条边到达的顶点，edge数组是这条边的长度，head数组是某个顶点的第一条边，net数组是下一条边 遍历的话，也附上代码吧（emmm）：

for(int k=1;k<=n;k++)//这里是遍历每个顶点的所有边 for(int i=head[k];i;i=next[i]) { //这里面进行你想要的操作 }

需要注意的是，Dijkstra算法只能用于无负边权的图，有负边权的话，它就不行了。（男人不能说不行 ） 算法的时间复杂度是O(n²),有点大呀。没关系，emmm，我们还有二叉堆优化。

Dijkstra的二叉堆优化： 顾名思义，就是用STL中的二叉堆维护dist数组，这样，在O(log n)的时间内就能获取最小值，然后再用O（log n）的时间执行一条边的扩展和更新。时间复杂度是O（mlog n）。 上代码：

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<queue> #include<vector> #define maxn 10005 using namespace std; int head[maxn*2],ver[maxn*2],edge[maxn*2],net[maxn*2],dist[maxn*2]; bool vis[maxn]; int n,m; int tot; priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > >q;//这里是小根堆，就是堆顶是最小值。同时，pair的第一维是dist值，第二维是节点编号。 void add(int x,int y,int z) //另外，二叉堆是先根据pair的第一个元素进行排序，第一个元素相同时再根据第二个 元素排序。 { ver[++tot]=y; edge[tot]=z; net[tot]=head[x]; head[x]=tot; } void dijkstra() { memset(dist,0x3f,sizeof(dist)); dist[1]=0; q.push(make_pair(0,1)); while(!q.empty()) { int node=q.top().second;//你要取的节点编号是第二个元素 q.pop();//没有利用价值了 emmm if(vis[node]) continue; vis[node]=true; for(int i=head[node];i;i=net[i])//遍历从node节点出发的所有边 { if(dist[ver[i]]>dist[node]+edge[i])//更新操作 { dist[ver[i]]=dist[node]+edge[i];//既然它被更新了，那么它就有机会去争夺最小的位置了。 q.push(make_pair(dist[ver[i]],ver[i]));//把这个节点的dist，编号加入二叉堆中 } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } dijkstra(); for(int i=2;i<=n;i++) printf("%d ",dist[i]); return 0; }

细心的小伙伴已经发现了，这里我们是用邻接表储存的图。对邻接表使用不明白的童鞋，可以看一下这段代码中使用邻接表的部分。

呼～ 终于讲完一个了。下面讲另外一个。

2.Bellman-Ford算法： 步骤：First：扫描所有边node->ver，边长为z，若dist[ver]>dist[node]+z,则用dist[node]+z更新dist[ver]。 Second：重复First，直到dist数组不发生改变。 上代码：

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define maxn 10005 int ver[maxn*2],head[maxn*2],net[maxn*2],edge[maxn*2],dist[maxn*2]; int n,m; int tot; using namespace std; void add(int x,int y,int z) { edge[++tot]=z; ver[tot]=y; net[tot]=head[x]; head[x]=tot; } void bellman() { memset(dist,0x3f,sizeof(dist)); dist[1]=0; for(int i=1;i<=n;i++) //n次检查 { for(int j=1;j<=n;j++) //检查这从n个顶点出发的m条边 { for(int k=head[j];k;k=net[k]) { dist[ver[k]]=min(dist[ver[k]],dist[j]+edge[k]);//更新操作 } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } bellman(); for(int i=2;i<=n;i++) printf("%d ",dist[i]); return 0; }

仔细阅读后，我们发现，bellman-ford和dijkstra代码不都差不多吗。emmm，好像是差不多，但它们的核心代码不一样哦。另外，bellman-ford的代码中没有用到标记数组，算法的时间复杂度是O(nm)，那么，有没有优化呢。。。当然是有啦。

其实，我们常用的SPFA算法就是Bellman-Ford算法的队列优化。 仔细想想，Bellman-Ford算法中存在着对不需要扩展的节点的扫描，那么，我们怎么避免呢？ 没错，就是用队列，emmm。 你想想，当你更新完一个dist后想把该节点加入队列，但是队列中该节点已经存在时，你会怎么做？ 当然是让它滚啦，emmm，就是不把它加入到我们的队列中。（一山不容二虎 ） 这样，我们就避免了不需要的扫描。

步骤：First：建立一个队列，把源点（1）放到队列中。 Second：取出队头节点node，扫描它的所有出边node->ver，边长为z，若dist[ver]>dist[node]+z,就用dist[node]+z来更新dist[ver]。若ver节点不在队列中，把ver节点入队。 Third：重复Second，直到队列为空。 上代码：

#include<iostream> #include<cstdio> #include<queue> #include<cmath> #include<cstring> #define maxn 10005 using namespace std; int ver[maxn*2],edge[maxn*2],net[maxn*2],head[maxn*2],dist[maxn*2]; bool vis[maxn]; int n,m; int tot; queue<int> q; void add(int x,int y,int z) { edge[++tot]=z; ver[tot]=y; net[tot]=head[x]; head[x]=tot; } void spfa() { memset(dist,0x3f,sizeof(dist)); dist[1]=0; q.push(1);//此时，队列中只有一号节点 vis[1]=1;//一号节点在队列中，标记一号节点 while(!q.empty())//队列非空 { int node=q.front();//取出队首 q.pop();//弹出队首 vis[node]=0;//队首已经不在队列中了，清空对它的标记 for(int i=head[node];i;i=net[i]) { if(dist[ver[i]]>dist[node]+edge[i]) { dist[ver[i]]=dist[node]+edge[i];//更新操作 if(!vis[ver[i]])//该节点不在队列中，把它加进去 { q.push(ver[i]); vis[ver[i]]=1;//标记 } } } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } spfa(); for(int i=2;i<=n;i++) printf("%d ",dist[i]); return 0; }

时间复杂度是O(km),其中，k是个较小的常数。

值得一提的是，Bellman-Ford算法和SPFA算法都能够解决带有负边权的图，至于为什么呢，emmm，你想想啊（想不出来 ），Dijkstra算法为什么不能解决带有负边权的图呢，因为带有负边权的话，你每次找最小的dist的时候，由于负边权的存在，你会一直更新同一个dist并且这个dist一直是最小的，如此，emmm，你的程序就炸了。而Bellman-Ford算法和SPFA中并没有去找dist数组中值最小的节点，也就没有上述隐患了。。。终于说完了。

基础知识掌握了之后，剩下的就是刷题了。建议先从模板刷起，之后逐步提升难度。

最后，宣传一下洛谷，一个非常nice的刷题的地方。