NOIP图的基础算法

1、noip 图的常用算法简介 石门中学江涛 2009.10.4目 录n图的表示邻接矩阵、邻接链表、图的遍历n最小生成树算法 prim算法、kruskal算法n最短路径算法dijkstra算法、bellman_ford算法及spfa算法、floyd算法目 录n图的表示邻接矩阵、邻接链表、图的遍历n最小生成树算法 prim算法、kruskal算法n最短路径算法dijkstra算法、bellman_ford算法及spfa算法、floyd算法n顶点顶点q给点编号为连续的整数q把顶点存放在数组中n边边q邻接矩阵n布尔值(或边权值) -true 有边false 无边n空间复杂度o(|v|2)图的表示-邻接矩

2、阵n边边q邻接链表n每一个顶点q有一个所有与之相邻的链表n每一条边q2 个（对无向图）q要在两个顶点的链表中都加入n空间复杂度o(|e|) 对稀疏图这种方式比较好图的表示-邻接链表 图的邻接链表的图的邻接链表的pascal和和c+实现实现 具体参见具体参见noip基础数据结构基础数据结构ppt图的表示-c/p语言程序实现图的深度优先图的深度优先(depth-first)遍历遍历:邻接链表、c+图的表示-图的遍历/图的一般结构图的一般结构 struct graph_node ; struct adjlist int id; adjlist *next; ; int n_nodes,s_index

3、=0; graph_node nodes maxn ; int visited maxn ; adjlist *adj maxn ;标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点邻接链表的节点数据结构数据结构图的深度优先图的深度优先(depth-first)遍历遍历:邻接链表、c+图的表示-图的遍历置每个点标识为置每个点标识为“未访问未访问”从所有未被访问从所有未被访问的点的点k出发，出发，调用调用dfs(k)void search( ) int k; for(k=0;kn_nodes;k+) visitedk = 0; for(k=0;knext) if ( !visitedj-id

4、 ) dfs( j-id ); 图的深度优先图的深度优先(depth-first)遍历遍历:邻接链表、pascal图的表示-图的遍历/图的一般结构图的一般结构 type graph_node=record end; type adjlist=record id :integer; next :adjlist; end; var n_nodes,s_i:integer; nodes:array1.maxn of graph_node; visited:array1.maxnof integer; adj:array1.maxn of adjlist;标识项点有没有访问过每个顶点都有邻接链表邻接链

5、表的节点邻接链表的节点数据结构数据结构图的深度优先图的深度优先(depth-first)遍历遍历:邻接链表、pascal图的表示-图的遍历置每个点标识为置每个点标识为“未访问未访问”从所有未被访问从所有未被访问的点的点k出发，出发，调用调用dfs(k)procedure search( ); begin k :integer; for k:=1 to n_nodes do visitedk:= 0; for k:=1 to n_nodes do if visitedk0 then dfs( k ); end;置被访问节点的置被访问节点的“时间时间”-次序次序访问访问k的所有相邻的节点的所有相邻

6、的节点 procedure dfs(k:integer);begin /从从k出发搜索出发搜索 var j:adjlist ;begin inc(s_i);visitedk:=s_i; j:=adjk; while (jnull) do begin if visitedj.id0 then dfs(j.id); j:=j.next;end; end;图的宽度优先图的宽度优先(breadth-first)遍历遍历:邻接链表、c+图的表示-图的遍历/图的一般结构图的一般结构 struct graph_node ; struct adjlist int id; adjlist *next; ; in

7、t n_nodes,s_index=0; graph_node nodes maxn ; int visited maxn ; adjlist *adj maxn ;标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点邻接链表的节点数据结构数据结构图的宽度优先图的宽度优先(breadth-first)遍历遍历:邻接链表、c+图的表示-图的遍历置每个点标识为置每个点标识为“未访问未访问”从所有未被访问从所有未被访问的点的点k出发，出发，调用调用bfs(k)void search( ) int k; for(k=0;kn_nodes;k+) visitedk = 0; for(k=0;kn_no

8、des;k+) if ( !visitedk ) bfs( k ); 图的宽度优先图的宽度优先(breadth-first)遍历遍历:邻接链表、c+图的表示-图的遍历int q maxn ;void bfs( int k ) int front,back; q0=k; front=back=0; for(;fronnext) if ( !visitedj-id ) q+back=j-id; visitedj-id=+s_index; bfs用的队列，一般全局front=back,队列不空访问访问k的所有相邻的节点的所有相邻的节点 图的宽度优先图的宽度优先(breadth-first)遍历实例示

9、意遍历实例示意:图的表示-图的遍历目 录n图的表示邻接矩阵、邻接链表、图的遍历n最小生成树算法 prim算法、kruskal算法n最短路径算法dijkstra算法、bellman_ford算法及spfa算法、floyd算法图的遍历图的遍历:邻接链表时间复杂度分析n每一个顶点访问一次每一个顶点访问一次n每条边访问两次每条边访问两次无向图每条边出现在两个链表中无向图每条边出现在两个链表中no(|v| + |e|) o(|v|2) 对对 稠密稠密图图 |e| |v|2 o(|v|) 对对 稀疏稀疏图图 |e| |v| 对稀疏图邻接链表的效果非常好！ 图的表示-图的遍历生成树生成树：一个：一个|v|个

10、点的图，取其中个点的图，取其中|v|-1条边，并连条边，并连接所有的顶点，则组成原图的一个接所有的顶点，则组成原图的一个生成树生成树。属性：属性：|v|-1条边、连通、无环。条边、连通、无环。最小生成树最小生成树：加权图的最小生成树是一棵：加权图的最小生成树是一棵生成树生成树，其，其所有边的权值之和不会大于其它任何生成树。所有边的权值之和不会大于其它任何生成树。简单讲：简单讲：找出连接所有点的最低成本路线找出连接所有点的最低成本路线最小生成树(mst)-定义红边连接了所有顶点红边连接了所有顶点,所以构成一棵生成树所以构成一棵生成树权和权和=1+2+4+4+7+8+9局域网局域网(net)rqn

11、oj 某局域网内有某局域网内有n(nn(n=100)=100)台计算机，由于建网时台计算机，由于建网时工作人员的疏忽，现在网内存在回路，造成网工作人员的疏忽，现在网内存在回路，造成网络卡的现象。络卡的现象。 我们用我们用f(i,jf(i,j) )表示表示i,ji,j之间连接的畅通程度之间连接的畅通程度( (f(i,jf(i,j)=1000)=1000)，f(i,jf(i,j) )值越小表示值越小表示i,ji,j之间连之间连接越通畅，接越通畅，f(i,jf(i,j) )为为0 0表示表示i,ji,j之间无网线连接。之间无网线连接。现在我们需要除去一些连线，使得网络中没有现在我们需要除去一些连线，

12、使得网络中没有回路，并且被除去网线的回路，并且被除去网线的f(i,jf(i,j) )最大，请求最大，请求出这个最大值。出这个最大值。最小生成树(mst)-实例一q环属性环属性：一棵生成树上，增加一条边：一棵生成树上，增加一条边e，再删除，再删除e所在环上的最大边，会得到另一棵所在环上的最大边，会得到另一棵“更好更好”的生成的生成树树(如果如果e不是最大边不是最大边)最小生成树(mst)-算法原理94q剪切属性剪切属性：在图中，剪切将顶点划分成两个不相：在图中，剪切将顶点划分成两个不相交集合。交叉边为地些顶点在两个不同集合的边。交集合。交叉边为地些顶点在两个不同集合的边。对于任何一个剪切，各条最

13、小的交叉边都属于某对于任何一个剪切，各条最小的交叉边都属于某个个mst，且每个，且每个mst中都包含一条最小交叉边。中都包含一条最小交叉边。最小生成树(mst)-算法原理749q最小边原则最小边原则：图中权值最小的边：图中权值最小的边(如果唯一的话如果唯一的话)一一定在最小生成树上。定在最小生成树上。q唯一性唯一性：一棵生成树上，如果各边的权都不相同，：一棵生成树上，如果各边的权都不相同，则最小生成树是唯一的。反之不然。则最小生成树是唯一的。反之不然。q思考思考：怎样图：怎样图g判断只有一个判断只有一个mst？最小生成树(mst)-算法原理q算法描述算法描述1：mst_prim(g, r) (

14、1)将将g剪切成两个集合剪切成两个集合a、b，a中只有一个点中只有一个点r (2)取最小权的交叉边取最小权的交叉边(x,y)，xb, yb (3)将将y加入加入a (4)如果已经加了如果已经加了n-1条边，结束。否则，转条边，结束。否则，转 (3)q算法证明算法证明： 根据剪切属性根据剪切属性 图图(?)最小生成树(mst)-prim算法q算法要点算法要点： 每次求最小权交叉边时，如果都重新计算，则每次求最小权交叉边时，如果都重新计算，则显然要枚举显然要枚举(x,y)- xa ,yb。o(n2)时间复杂时间复杂度。度。 其实每次其实每次a中只是增加一个新顶点中只是增加一个新顶点v，最多有交，最

15、多有交叉边叉边(v,y)，修改量只有与，修改量只有与v有边的顶点，为有边的顶点，为o(n)。 只需记录下只需记录下b中的每个元素中的每个元素y与与a所有元素中最所有元素中最小权边，则求最小值最多为小权边，则求最小值最多为o(n)-有时有时可以用可以用“堆堆”优化。优化。 最小生成树(mst)-prim算法q算法描述算法描述2：mst_prim(g, r) /从任意点从任意点r出发，生长成一出发，生长成一mst for i=1 to n do disi / 初始化每点到初始化每点到a集合的最小值集合的最小值 inai false /设顶点不在设顶点不在a中中disr 0 /将将r设为设为0（或（

16、或- ），准备取出），准备取出for i=1 to n do v get-min() /取取dis?中最小的值中最小的值c和顶点和顶点v, ina v true /v放入放入a中中 sum sum+c /c加入加入mst的总和中的总和中 updata( v ) /枚举交叉边枚举交叉边(v,b),改进改进dis 最小生成树(mst)-prim算法q算法描述算法描述3：mst_kruskal(g) (1)将将g所有条边按权从小到大排序；图所有条边按权从小到大排序；图mst开始为空开始为空 (2)从小到大次序取边从小到大次序取边(x,y) (3)若加入边若加入边(x,y)，mst就有环，则放弃此边，

17、转就有环，则放弃此边，转(2) (4)将边将边(x,y)加入加入mst，如果已经加了，如果已经加了n-1条边，结束。条边，结束。否则，转否则，转 (2)q算法证明算法证明： 根据剪切属性根据剪切属性 图图(?)最小生成树(mst)-kruskal算法q算法要点算法要点： kruskal算法的最难点在于怎样判断加入边算法的最难点在于怎样判断加入边(x,y)后是否形成了环。后是否形成了环。q问题可化为问题可化为： 判断边判断边(x,y)的两个顶点的两个顶点x,y在图（实际是森林）在图（实际是森林）mst中最否已经连通。如果已经连通，加入边将中最否已经连通。如果已经连通，加入边将形成环；否则，不形成

18、环。形成环；否则，不形成环。q 并查集并查集： 连通点集之类问题，有高效算法连通点集之类问题，有高效算法-并查集并查集。最小生成树(mst)- kruskal算法q并查集并查集： 并查集详细内容可参见有关文章。下面是并查集详细内容可参见有关文章。下面是pascal段：段：/初始化，使每个集合只一个元素。初始化，使每个集合只一个元素。 for i:=1 to n do f i :=i;/查找查找x所在类的所在类的“根根”-代表，并压缩路径代表，并压缩路径function find_set(x:longint):longint; begin if fxx then fx:=find_set(fx)

19、; exit(fx);end;/合并两个集合。合并两个集合。x,y为两集合的为两集合的“根根”procedure union(x,y:longint); begin fx:=y;end;最小生成树(mst)- kruskal算法q并查集并查集： 并查集详细内容可参见有关文章。下面是并查集详细内容可参见有关文章。下面是c+片段：片段：/初始化，使每个集合只一个元素。初始化，使每个集合只一个元素。 for (i=1;i = n ; i+) f i = i;/查找查找x所在类的所在类的“根根”-代表，并压缩路径代表，并压缩路径int find_set ( int x) if (fx != x) fx

20、 = find_set( fx ); return (fx);/合并两个集合。合并两个集合。x,y为两集合的为两集合的“根根”void union(int x,y ) fx = y;最小生成树(mst)- kruskal算法q算法描述算法描述4：mst_kruskal(g) for i=1 to n do fi i; /初始化并查集初始化并查集 sort( e, e+m); /边按大小排序边按大小排序c 0; /取边的计数器取边的计数器for i=1 to m do /从小到大取边从小到大取边 v find_set( ei.v ); /左端点所在连通块左端点所在连通块“根根” u find_s

21、et( ei.u ); /右端点所在连通块右端点所在连通块“根根” if(v != u) /如果不在同一连通块如果不在同一连通块 union(v,u); /合并两连通块合并两连通块 sum += gvu; /加入这条边的权加入这条边的权 if (+c = n-1) break; /if 取了取了n-1条边，结束条边，结束最小生成树(mst)-kruskal算法时间复杂度分析时间复杂度分析nprim算法普通的方法算法普通的方法 o(|v|2) nprim算法中用算法中用“堆堆”方法方法 o(|e|+|v|)*log|v|) -对稀疏图较好对稀疏图较好nkruskal算法算法 o(|e|*log|

22、e| +|n|*a(|v|) -对稀疏图较好对稀疏图较好最小生成树(mst)-时间复杂度1 1、平面上有、平面上有n(=3000)n(=3000)个点，求连通它们个点，求连通它们的最小生成树，用什么算法比较好？的最小生成树，用什么算法比较好？2 2、要判断一条边是否可以在一棵、要判断一条边是否可以在一棵mstmst上，上，怎样做比较好？怎样做比较好？3 3、平面上有、平面上有k k个水源（井），个水源（井），n n个居民供水个居民供水点，怎样用最少的管道使这点，怎样用最少的管道使这n n个居民点都个居民点都能用连接到水源。注：边只能水源、居民能用连接到水源。注：边只能水源、居民点之间直接相连。

23、点之间直接相连。最小生成树(mst)-思考题 maintain 有一个无向图，有有一个无向图，有n个点个点 ，有，有w条边。但条边。但是一开始，所有的边都是被破坏了的，即不是一开始，所有的边都是被破坏了的，即不可用。接下来每一天可以修复一条边。注意：可用。接下来每一天可以修复一条边。注意：两个点之间可能有多条边。两个点之间可能有多条边。 现在的问题是：每一天修复完一条边后，现在的问题是：每一天修复完一条边后，无向图中的任意两个结点都可以连通了吗？无向图中的任意两个结点都可以连通了吗？如果还不可以输出如果还不可以输出-1，如果可以了，你从已，如果可以了，你从已经修复的边中，选择一些边，使得这些边

24、的经修复的边中，选择一些边，使得这些边的总长度最小，输出最小值。总长度最小，输出最小值。最小生成树(mst)-实例二输入格式：输入格式：q第一行第一行: 两个整数：两个整数：n，w。 n (1=n=200) 、 w (1 = w e.c ，删除边，删除边x,加入边加入边e. m*n 1,200,000q简化算法？简化算法？ 由于每次只保留由于每次只保留n-1条边，每次重新做条边，每次重新做kruskal算算法：法：m*n*logn 9,600,000 大致可行。大致可行。更可省略更可省略排序，用插入法即可排序，用插入法即可： m*n*3 = disy q 松驰松驰 若在处理过程中，有两点若在处

25、理过程中，有两点x、y出现不符合出现不符合“三角三角形定理形定理”，则可改进一下，则可改进一下松驰松驰： if ( disx+lenxy =0,如果如果disv disx，则，则x永远不会松驰永远不会松驰v，故，故v点确定点确定下来。下来。最短路径-dijkstra算法算法sxvdisvdisxa集合集合b集合集合n第一步，初始化第一步，初始化所有顶点所有顶点距离置距离置 源点源点置置 0 最短路径-dijkstra算法算法n第二步，取出第二步，取出s，松驰相邻点，松驰相邻点松驰松驰s的相邻顶点的相邻顶点最短路径-dijkstra算法算法源点源点红箭头表示方案前趋点红箭头表示方案前趋点s放入放

26、入a集合集合取最近的顶点取最近的顶点x最短路径-dijkstra算法算法n第三步第三步由对由对u松驰松驰由由x对对y松驰松驰最短路径-dijkstra算法算法n第四步第四步a = s, x 选选b中最近的点中最近的点y最短路径-dijkstra算法算法n第五步第五步a = s, x, y 选选b中最近点中最近点 u最短路径-dijkstra算法算法n第六步第六步a = s, x, y, u 最后选择最后选择 v最短路径-dijkstra算法算法n第七步第七步a = s, x, y, u 红色箭头记录的是最短路径的红色箭头记录的是最短路径的前趋点。前趋点。 最短路径-dijkstra算法算法n第

27、八步第八步q算法描述算法描述2：sp_dijkstra(g, s) /求单源求单源s到其它点的最短距离到其它点的最短距离 for i=1 to n do disi / 初始化每点到初始化每点到s距离距离 inai false /设顶点不在设顶点不在a中中diss 0 /将将diss设为设为0，准备取出，准备取出for i=1 to n do v get-min() /取取dis?中最小的值中最小的值c和顶点和顶点v, ina v true /v放入放入a中中 sum sum+c /c加入加入mst的总和中的总和中 updata( v ) /检查检查(v,b),松驰松驰dis? 最短路径-dij

28、kstra算法算法与与prim不相不相同点同点cooking bessie喜欢为在外面的奶牛做晚餐，喜欢为在外面的奶牛做晚餐，bessie按按响铃给他们一个信号叫他们进来就可以了。响铃给他们一个信号叫他们进来就可以了。 晚餐将在晚餐将在t (1 = t = 1,000,000)毫秒完成，而毫秒完成，而且且bessie强调那些想吃她晚餐的奶牛必须准时到。强调那些想吃她晚餐的奶牛必须准时到。 这些牛在这些牛在f (1 = f = 500)各不同的草地标号为各不同的草地标号为1f用用p(1 = p = 10,000)个双向的小路连接。个双向的小路连接。 bessie在第在第1个草地，个草地， 给出一

29、头牛走每一条小路给出一头牛走每一条小路所用的时间，问多少个草地上的奶牛可以在所用的时间，问多少个草地上的奶牛可以在t毫秒毫秒内到内到bessie 所在的草地，假设多头牛可以共享一所在的草地，假设多头牛可以共享一条路。条路。最短路径-实实例一例一 如果边有如果边有负权负权的话，的话，dijkstra算法算法是错误的。这是错误的。这里需要不断里需要不断迭代迭代地做地做“松驰松驰”，直到无，直到无“松驰松驰”为为止。止。q算法描述算法描述3：sp_bellman(g, s) (1)初始化每点到初始化每点到s点的最短距离为点的最短距离为 (2)取所有边取所有边(x,y)，看，看x能否对能否对y松驰。松

30、驰。 (3)如果没有任何松驰，则结束如果没有任何松驰，则结束break。 (4)如果松驰次数如果松驰次数n，转，转(2) (5)否则，图中有否则，图中有“负圈负圈”。最短路径-bellman-ford算法算法算法说明算法说明：qbellman-ford算法算法n次迭代就可以判断图中是否有次迭代就可以判断图中是否有“负环负环”。q取所有边有两种方法：取所有边有两种方法： (1)扫描每一点的邻接链表扫描每一点的邻接链表 (2)用有序点对用有序点对(x,y)记录边时，可直接取边。但要记录边时，可直接取边。但要请注意对无向图，要注意请注意对无向图，要注意(y,x)也要松驰。也要松驰。q对于求对于求s到

31、某点到某点t的最短距离，可能因为其它地方有的最短距离，可能因为其它地方有“负环负环”而出现问题，要预处理。而出现问题，要预处理。最短路径-bellman-ford算法算法q算法描述算法描述4：sp_bellman(g, s) /求单源求单源s到其它点的最短距离到其它点的最短距离 for i=1 to n do disi / 初始化每点到初始化每点到s距离距离diss 0 /将将diss设为设为0for i=1 to n do /最多迭代最多迭代n rel=false; /是否有松驰标志是否有松驰标志 for 每条边每条边(x,y) /取图的每一条边取图的每一条边 if( disx+lenxyd

32、isy) /不满足三角形性质不满足三角形性质 disy=disx+lenxy; /松驰松驰disy rel=true; if rel = false return 0; /没有一次松驰，则结束没有一次松驰，则结束return -1; /迭代了迭代了n次，有负圈次，有负圈 最短路径- bellman-ford算法算法虫洞虫洞(wormholes) 在一个神秘岛上，有在一个神秘岛上，有n(1 = n = 500)个洞口，个洞口，标号标号1.n，它们之间有，它们之间有m (1 = m = 2500) 条通条通道相连。神秘的是另外还有道相连。神秘的是另外还有w (1 = w = 200)条传说中的时间

33、虫洞条传说中的时间虫洞-当到达通道的另一端洞当到达通道的另一端洞口时，竟然可以比进入的时间要早！口时，竟然可以比进入的时间要早！ 你当然想进行这样的时间之旅，希望从一个洞你当然想进行这样的时间之旅，希望从一个洞口口s出发，经过几个通道，在比出发早些时候的出发，经过几个通道，在比出发早些时候的时间回到洞口时间回到洞口s。也许还能碰到自己。也许还能碰到自己,hehe 根据给定的地图，请判断能否实现这样的愿望。根据给定的地图，请判断能否实现这样的愿望。最短路径-实实例二例二输入格式：输入格式： 第一行：第一行：一个整数一个整数 f (1 = f = 5)，表示共有，表示共有f组数据。组数据。（多组数

34、据测试）每组数据：（多组数据测试）每组数据：第第1行行：三个整数：三个整数 n m w 第第2至至m+1行行:每行三个整数每行三个整数 (s, e, t),表示在表示在s与与e洞口之洞口之间有一个间有一个双向双向通道，通过需要通道，通过需要t(0 = t = 10,000) 秒。秒。 第第m+2至至m+w+1行行:每行三个整数每行三个整数 (s, e, t),表示在表示在s与与e洞口之间有一个洞口之间有一个单向单向通道，从通道，从s到到e可以回到之前可以回到之前t(0 = t = 10,000) 秒。秒。输出格式：输出格式： 共共1.f行行，每行对应一组数据，如果可以实现愿望输出，每行对应一组

35、数据，如果可以实现愿望输出yes,否则输出否则输出no.最短路径-实实例二例二输入样例输入样例(wormhole.in):23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8最短路径-实实例二例二输出样例输出样例(wormhole.out):noyes 1233图图2481232413图图1分析分析q 首先，把无向边改成两个有向边，这样整个问题成在首先，把无向边改成两个有向边，这样整个问题成在有向图中求负环问题。有向图中求负环问题。 n*(m+w) = 500*（2500+200）0) do v qhead; /队头节点队头节点v for 每条边每条边(

36、v,i) /与与v相连的每一条边相连的每一条边 if( disv+lenvidisi) /不满足三角形性质不满足三角形性质 disi disv+lenvi; /松驰松驰disi if (visi = false) /不在队列，则加入队列不在队列，则加入队列 visi true; count+1; tail+1; qtail = i; visv false;head+1;count-1; /v出队列出队列最短路径- spfa算法算法spfa算法的思考算法的思考 q对有向图，对有向图，s到到t的最短路问题仍然有负环影响。无的最短路问题仍然有负环影响。无向图呢？向图呢？q怎样判断图上负环？怎样判断图

37、上负环？ 最短路径-spfa算法算法q求每对节点之间最短距离问题：例如，求一个图的求每对节点之间最短距离问题：例如，求一个图的直径，即所有最短路径中最长的。直径，即所有最短路径中最长的。q 如果多次调用单源最短路径算法，效果并不好。如果多次调用单源最短路径算法，效果并不好。特别是对有负边的图。特别是对有负边的图。q如果如果无负环无负环，则有简单的，则有简单的floyd-warshell算法。这算法。这是动态规划算法。是动态规划算法。最短路径-floyd算法算法动态规划算法动态规划算法n定义定义d i ,j , k 为为q路径中间只允许经过节点1k的情况下qi到j的最短路距离n它有两种情况它有两

38、种情况q最短路经过点k，di,j,k=di,k,k-1+dk,j,k-1q最短路不经过点k，di,j,k=di,j,k-1n 综合起来，状态转移方程为综合起来，状态转移方程为 di,j,k=min di,k,k-1 + dk,j,k-1,di,j,k-1 n边界条件边界条件 di,j,0=lenij（不存在的边权可为）最短路径-floyd算法算法算法描述算法描述6：sp_floyd( g ) /求每对节点的最短距离求每对节点的最短距离 for i=1 to n do for j=1 to n do disi,j lenij; / 初始化边界条件初始化边界条件for k=1 to n do /k

39、放在最外层，数组少一维放在最外层，数组少一维 for i=1 to n do for j=1 to n do if( disi,k+diskjdisi,j) /状态转移状态转移 disi,j disik+diskj; 最短路径- floyd算法算法floyd算法的思考算法的思考qfloyd算法怎样记录下最短路径？算法怎样记录下最短路径？qfloyd算法怎样判断负环？算法怎样判断负环？q求图中的最小环问题。求图中的最小环问题。最短路径-floyd算法算法ndijkstraq单源单源 非负非负 o(|v|2) 对稠密图好对稠密图好q可用可用“堆堆”优化优化 o(|e|*log|v|) 对稀疏图较好

40、对稀疏图较好nbellman-fordq单源单源 无负环无负环 o(|v|*|e|)q可先用可先用dijkstra预处理优化预处理优化qspfa用更新队列优化用更新队列优化,时间复杂度平均好，但不确定。时间复杂度平均好，但不确定。nfloydq全源全源 无负环无负环 o(|v|2)思考：思考：有多源问题类吗？有多源问题类吗？ 如果边权只有如果边权只有0,1(或或0,1,2,3,4)，能否优化算法？，能否优化算法？最短路径-算法比算法比较较最短路径-实实例三例三butter 农夫农夫johnjohn发现做出全威斯康辛州最甜的黄油的发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知

41、道方法：糖。把糖放在一片牧场上，他知道n n只奶牛只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。会过来舔它，这样就能做出能卖好价钱的超甜黄油。 农夫农夫johnjohn可以训练这些奶牛，让它们在听到铃可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。下午发出铃声，以至他可以在晚上挤奶。 农夫农夫johnjohn知道每只奶牛都在各自喜欢的牧场知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛所在（一个牧场不一定只有一头牛）。给出各头牛所在的牧场和牧场间的路线，找出使

42、所有牛到达的路程的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）和最短的牧场（他将把糖放在那）最短路径-实实例三例三输入格式输入格式 第一行第一行: 三个数，奶牛数三个数，奶牛数n（1=n=500）, 牧场牧场数数p（2=p=800），牧场间道路数），牧场间道路数c (1=c=1450) 第二行到第第二行到第n+1行行: 1 到到 n 头奶牛所在的牧场号头奶牛所在的牧场号 第第n+2行到第行到第n+c+1行行： 每行有三个数每行有三个数,相连的牧相连的牧场场a、b，两牧场间距离，两牧场间距离d（1=d5*108要超时。要超时。 边比较少，可枚举每一点为源，再用边比较少，可枚举每一点为源，再用dijkstra算法算法+堆优化来处理堆优化来处理: p*c*logp =800* 1450*log8001.2*107 不超时不超时 参考程序见附件参考程序见附件参考程序参考程序101.do