提高组精英班 2017清北学堂集训笔记——图论( 四 ) _最小生成树

文章插图
②i和j间接联通，中间有k号节点联通：

文章插图
假设dis[i][j]表示从i到j的最短路径，对于存在的每个节点k，我们检查一遍dis[i][k]+dis[k][j] 。
1 //Floyd算法，时间复杂度：O(n^3)2 int dis[MAXN][MAXN]; 3 for(k=1;k<=n;k++)//枚举4 { 5for(i=1;i<=n;i++) 6{ 7for(j=1;j<=n;j++) 8{ 9dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//DP10}11}12 }
2.算法（无向图，无负权边）：
算法描述：
多源最短路！
a.初始时，S只包含源点，即S＝{v}，v的距离为0 。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则正常有权值，若u不是v的出边邻接点，则权值为∞ 。
b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
d.重复步骤b和c直到所有顶点都包含在S中。
啊~上面的的乱七八糟的概念太难懂了，还是举个例子吧！如下图！

文章插图
我们假设1号节点为原点。
第一轮，我们可以算出2,3,4,5,6号节点到原点1的距离为[7,9,∞,∞,14]，∞表示无穷大（节点间无法直接连通），取其中最小的7，就确定了1->1的最短路径为0，1->2的最短路径为7，同时取最短路径最小的2节点为下一轮的前驱节点。
第二轮，取2节点为前驱节点，按照前驱节点到原点的最短距离 + 新节点到前驱节点的距离来计算新的最短距离，可以得到3,4,5,6号节点到原点1的距离为[17,22,∞,∞]（新节点必须经过2号节点回到原点），这时候需要将新结果和上一轮计算的结果比较，3号节点：17>9，最短路径仍然为9；4号节点：223->6的最短路径为11，同时取最短路径最小的6节点为下一轮的前驱节点。
第四轮：同理，得到4,5号节点最短距离为[20,20]，这两个值相等，运算结束，到达这两个点的最短距离都是20，如果这两个值不相等，还要进行第五轮运算！
1 #include 2 #include 3 const int N=100500; 4 const int M=200500; 5 int point[N]={0},to[M]={0},next[M]={0},len[M]={0},cc=0; 6 int dis[N];//最短路长度，dis[i]表示第i号点到源点（1号点）的最短距离 7 bool ever[N];//当前节点最短路有没有确定8 int n,m;9 void AddEdge(int x,int y,int z)//添加新的边和节点：x到y边长z10 {11cc++;12next[cc]=point[x];13point[x]=cc;14to[cc]=y;15len[cc]=z;//len记录x到y的边长 16 }17 int main()18 {19int i,j,k;20scanf("%d%d",&n,&m);21for(i=1;i<=m;i++)22{23int a,b,c;24scanf("%d%d%d",&a,&b,&c);25AddEdge(a,b,c);//无向图，要加两遍 26AddEdge(b,a,c);27}28memset(dis,0x3f,sizeof dis);//用极大值来初始化 29dis[1]=0;//1号节点到自己最短距离为0 30for(k=1;k<=n;k++)31{32int minp,minz=123456789;33for(i=1;i<=n;i++)34{35if(!ever[i])36{37if(dis[i]dis[minp]+len[now])50dis[tox]=dis[minp]+len[now];51now=next[now];52}53}54for(i=1;i<=n;i++)55printf("%d\n",dis[i]);56return 0;57 }
3.SPFA算法（有负权边，无负圈，能检测负圈但不能输出）：
多源最短路！
SPFA和极为相似，只是加了个队列优化来检测负圈和负权边。
算法描述：
建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。