flash源码网站,天水+网站建设,网站根目录表示,推广网站加盟暑假#xff0c;小哼准备去一些城市旅游。有些城市之间有公路#xff0c;有些城市之间则没有#xff0c;如下图。为了节省经费以及方便计划旅程#xff0c;小哼希望在出发之前知道任意两个城市之前的最短路程。上图中有4个城市8条公路#xff0c;公路上的数字表示这条公路… 暑假小哼准备去一些城市旅游。有些城市之间有公路有些城市之间则没有如下图。为了节省经费以及方便计划旅程小哼希望在出发之前知道任意两个城市之前的最短路程。上图中有4个城市8条公路公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。 现在需要一个数据结构来存储图的信息我们仍然可以用一个4*4的矩阵二维数组e来存储。比如1号城市到2号城市的路程为2则设e[1][2]的值为2。2号城市无法到达4号城市则设置e[2][4]的值为∞。另外此处约定一个城市自己是到自己的也是0例如e[1][1]为0具体如下。现在回到问题如何求任意两点之间最短路径呢通过之前的学习我们知道通过深度或广度优先搜索可以求出两点之间的最短路径。所以进行n2遍深度或广度优先搜索即对每两个点都进行一次深度或广度优先搜索便可以求得任意两点之间的最短路径。可是还有没有别的方法呢 我们来想一想根据我们以往的经验如果要让任意两点例如从顶点a点到顶点b之间的路程变短只能引入第三个点顶点k并通过这个顶点k中转即a-k-b才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢甚至有时候不只通过一个点而是经过两个点或者更多点中转会更短即a-k1-k2b-或者a-k1-k2…-k-i…-b。比如上图中从4号城市到3号城市4-3的路程e[4][3]原本是12。如果只通过1号城市中转4-1-3路程将缩短为11e[4][1]e[1][3]5611。其实1号城市到3号城市也可以通过2号城市中转使得1号到3号城市的路程缩短为5e[1][2]e[2][3]235。所以如果同时经过1号和2号两个城市中转的话从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。好下面我们将这个问题一般化。当任意两点之间不允许经过第三个点时这些城市之间最短路程就是初始路程如下。如现在只允许经过1号顶点求任意两点之间的最短路程应该如何求呢只需判断e[i][1]e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]e[1][j]表示的是从i号顶点先到1号顶点再从1号顶点到j号顶点的路程之和。其中i是1~n循环j也是1~n循环代码实现如下。 1 2 3 4 5 6 7 8 for(i1;in;i) { for(j1;jn;j) { if ( e[i][j] e[i][1]e[1][j] ) e[i][j] e[i][1]e[1][j]; } } 在只允许经过1号顶点的情况下任意两点之间的最短路程更新为通过上图我们发现在只通过1号顶点中转的情况下3号顶点到2号顶点e[3][2]、4号顶点到2号顶点e[4][2]以及4号顶点到3号顶点e[4][3]的路程都变短了。 接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢我们需要在只允许经过1号顶点时任意两点的最短路程的结果下再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]e[2][j]是否比e[i][j]要小代码实现为如下。 1 2 3 4 5 6 7 8 //经过1号顶点 for(i1;in;i) for(j1;jn;j) if (e[i][j] e[i][1]e[1][j]) e[i][j]e[i][1]e[1][j]; //经过2号顶点 for(i1;in;i) for(j1;jn;j) if (e[i][j] e[i][2]e[2][j]) e[i][j]e[i][2]e[2][j]; 在只允许经过1和2号顶点的情况下任意两点之间的最短路程更新为通过上图得知在相比只允许通过1号顶点进行中转的情况下这里允许通过1和2号顶点进行中转使得e[1][3]和e[4][3]的路程变得更短了。同理继续在只允许经过1、2和3号顶点进行中转的情况下求任意两点之间的最短路程。任意两点之间的最短路程更新为最后允许通过所有顶点作为中转任意两点之间最终的最短路程为整个算法过程虽然说起来很麻烦但是代码实现却非常简单核心代码只有五行 1 2 3 4 5 for(k1;kn;k) for(i1;in;i) for(j1;jn;j) if(e[i][j]e[i][k]e[k][j]) e[i][j]e[i][k]e[k][j]; 这段代码的基本思想就是最开始只允许经过1号顶点进行中转接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转求任意两点之间的最短路程。用一句话概括就是从i号顶点到j号顶点只经过前k号点的最短路程。其实这是一种“动态规划”的思想关于这个思想我们将在《啊哈算法2——伟大思维闪耀时》在做详细的讨论。下面给出这个算法的完整代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include stdio.h int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值 //读入n和mn表示顶点个数m表示边的条数 scanf(%d %d,n,m); //初始化 for(i1;in;i) for(j1;jn;j) if(ij) e[i][j]0; else e[i][j]inf; //读入边 for(i1;im;i) { scanf(%d %d %d,t1,t2,t3); e[t1][t2]t3; } //Floyd-Warshall算法核心语句 for(k1;kn;k) for(i1;in;i) for(j1;jn;j) if(e[i][j]e[i][k]e[k][j] ) e[i][j]e[i][k]e[k][j]; //输出最终的结果 for(i1;in;i) { for(j1;jn;j) { printf(%10d,e[i][j]); } printf(\n); } return 0; } 有一点需要注意的是如何表示正无穷。我们通常将正无穷定义为99999999因为这样即使两个正无穷相加其和仍然不超过int类型的范围C语言int类型可以存储的最大正整数是2147483647。在实际应用中最好估计一下最短路径的上限只需要设置比它大一点既可以。例如有100条边每条边不超过100的话只需将正无穷设置为10001即可。如果你认为正无穷和其它值相加得到一个大于正无穷的数是不被允许的话我们只需在比较的时候加两个判断条件就可以了请注意下面代码中带有下划线的语句。 1 2 3 4 5 6 //Floyd-Warshall算法核心语句 for(k1;kn;k) for(i1;in;i) for(j1;jn;j) if(e[i][k]inf e[k][j]inf e[i][j]e[i][k]e[k][j]) e[i][j]e[i][k]e[k][j]; 上面代码的输入数据样式为 1 2 3 4 5 6 7 8 9 4 8 1 2 2 1 3 6 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12 第一行两个数为n和mn表示顶点个数m表示边的条数。接下来m行每一行有三个数t1、t2 和t3表示顶点t1到顶点t2的路程是t3。得到最终结果如下通过这种方法我们可以求出任意两个点之间最短路径。它的时间复杂度是O(N3)。令人很震撼的是它竟然只有五行代码实现起来非常容易。正是因为它实现起来非常容易如果时间复杂度要求不高使用Floyd-Warshall来求指定两点之间的最短路或者指定一个点到其余各个顶点的最短路径也是可行的。当然也有更快的算法请看下一节Dijkstra算法。另外需要注意的是Floyd-Warshall算法不能解决带有“负权回路”或者叫“负权环”的图因为带有“负权回路”的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1-2-3-1-2-3-…-1-2-3这样路径中每绕一次1--23这样的环最短路就会减少1永远找不到最短路。其实如果一个图中带有“负权回路”那么这个图则没有最短路。此算法由Robert W. Floyd罗伯特·弗洛伊德于1962年发表在“Communications of the ACM”上。同年Stephen Warshall史蒂芬·沃舍尔也独立发表了这个算法。Robert WFloyd这个牛人是朵奇葩他原本在芝加哥大学读的文学但是因为当时美国经济不太景气找工作比较困难无奈之下到西屋电气公司当了一名计算机操作员在IBM650机房值夜班并由此开始了他的计算机生涯。此外他还和J.W.J. Williams威廉姆斯于1964年共同发明了著名的堆排序算法HEAPSORT。堆排序算法我们将在第七章学习。Robert WFloyd在1978年获得了图灵奖。 转载http://ahalei.blog.51cto.com/4767671/1383613
