《NOIP图的基础算法》ppt课件

1、NOIP 图的常用算法简介 石门中学江涛 2021.10.4目 录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法 Prim算法、Kruskal算法最短途径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法目 录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法 Prim算法、Kruskal算法最短途径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法顶点给点编号为延续的整数把顶点存放在数组中边邻接矩阵布尔值(或边权值) -TRUE 有边FALSE 无边空间复杂度O(|V|2)图的表示-邻接矩阵边边邻接链表邻接链表每一个顶点

2、每一个顶点有一个一切与之相邻的链表有一个一切与之相邻的链表每一条边每一条边2 个对无向图个对无向图要在两个顶点的链表中都参与要在两个顶点的链表中都参与空间复杂度空间复杂度O(|E|) 对稀疏图这种方式比较好对稀疏图这种方式比较好图的表示-邻接链表 图的邻接链表的图的邻接链表的Pascal和和C+实现实现 详细参见详细参见ppt图的表示-C/P言语程序实现图的深度优先图的深度优先(Depth-First)遍历遍历:邻接链表、邻接链表、C+图的表示-图的遍历/图的普通构造图的普通构造 struct graph_node ; struct AdjList int id; AdjList *next;

3、 ; int n_nodes,S_index=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=

4、0;knext) if ( !visitedj-id ) 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

5、AdjList;标识项点有没有访问过每个顶点都有邻接链表邻接链表的节点邻接链表的节点数据构造数据构造图的深度优先图的深度优先(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;置被访问节点的置

6、被访问节点的“时间时间-次序次序访问访问k的一切相邻的节点的一切相邻的节点 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 ; str

7、uct AdjList int id; AdjList *next; ; int 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

8、=0;kn_nodes;k+) visitedk = 0; for(k=0;kn_nodes;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的

9、一切相邻的节点的一切相邻的节点 图的宽度优先图的宽度优先(Breadth-First)遍历实例表示遍历实例表示:图的表示-图的遍历目 录图的表示邻接矩阵、邻接链表、图的遍历最小生成树算法 Prim算法、Kruskal算法最短途径算法Dijkstra算法、Bellman_Ford算法及SPFA算法、Floyd算法图的遍历图的遍历:邻接链表邻接链表时间复杂度分析时间复杂度分析每一个顶点访问一次每一个顶点访问一次每条边访问两次每条边访问两次无向图每条边出如今两个链表中无向图每条边出如今两个链表中O(|V| + |E|) O(|V|2) 对对 稠密图稠密图 |E| |V|2 O(|V|) 对对 稀疏图

10、稀疏图 |E| |V| 对稀疏图邻接链表的效果非常好！对稀疏图邻接链表的效果非常好！ 图的表示-图的遍历生成树：一个生成树：一个|V|个点的图，取其中个点的图，取其中|V|-1条边，并衔条边，并衔接一切的顶点，那么组成原图的一个生成树。接一切的顶点，那么组成原图的一个生成树。属性：属性：|v|-1条边、连通、无环。条边、连通、无环。最小生成树：加权图的最小生成树是一棵生成树，其最小生成树：加权图的最小生成树是一棵生成树，其一切边的权值之和不会大于其它任何生成树。一切边的权值之和不会大于其它任何生成树。简单讲：找出衔接一切点的最低本钱道路简单讲：找出衔接一切点的最低本钱道路最小生成树(MST)-

11、定义红边衔接了一切顶点红边衔接了一切顶点,所以构成一棵生成树所以构成一棵生成树权和权和=1+2+4+4+7+8+9局域网局域网(net)RQNOJ 某局域网内有某局域网内有n(n=100)台计算机，由于台计算机，由于建网时任务人员的忽略，如今网内存在回建网时任务人员的忽略，如今网内存在回路，呵斥网络卡的景象。路，呵斥网络卡的景象。 我们用我们用f(i,j)表示表示i,j之间衔接的畅通程度之间衔接的畅通程度(f(i,j)=1000)，f(i,j)值越小表示值越小表示i,j之间衔之间衔接越通畅，接越通畅，f(i,j)为为0表示表示i,j之间无网线衔之间无网线衔接。如今我们需求除去一些连线，使得网接

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

13、任何一个剪切，各条最小的交叉边都属于某对于任何一个剪切，各条最小的交叉边都属于某个个MST，且每个，且每个MST中都包含一条最小交叉边。中都包含一条最小交叉边。最小生成树(MST)-算法原理749q最小边原那么：图中权值最小的边最小边原那么：图中权值最小的边(假设独一的话假设独一的话)一定在最小生成树上。一定在最小生成树上。q独一性：一棵生成树上，假设各边的权都不一样，独一性：一棵生成树上，假设各边的权都不一样，那么最小生成树是独一的。反之不然。那么最小生成树是独一的。反之不然。q思索：怎样图思索：怎样图G判别只需一个判别只需一个MST？最小生成树(MST)-算法原理q算法描画算法描画1：qM

14、ST_Prim(G, r)q (1)将将G剪切成两个集合剪切成两个集合A、B，A中只需一个点中只需一个点rq (2)取最小权的交叉边取最小权的交叉边(x,y)，xB, yBq (3)将将y参与参与Aq (4)假设曾经加了假设曾经加了n-1条边，终了。否那么，转条边，终了。否那么，转 (3)q算法证明：算法证明：q 根据剪切属性根据剪切属性 图图(?)最小生成树(MST)-Prim算法q算法要点：算法要点：q 每次求最小权交叉边时，假设都重新计算，每次求最小权交叉边时，假设都重新计算，那么显然要枚举那么显然要枚举(x,y)- xA ,yB。O(n2)时间时间复杂度。复杂度。 q 其实每次其实每次

15、A中只是添加一个新顶点中只是添加一个新顶点v，最多，最多有交叉边有交叉边(v,y)，修正量只需与，修正量只需与v有边的顶点，为有边的顶点，为O(n)。q 只需记录下只需记录下B中的每个元素中的每个元素y与与A一切元素一切元素中最小权边，那么求最小值最多为中最小权边，那么求最小值最多为O(n)-有时可有时可以用以用“堆优化。堆优化。q 最小生成树(MST)-Prim算法q算法描画算法描画2：qMST_Prim(G, r) /从恣意点从恣意点r出发，生长成一出发，生长成一MSTq for i=1 to n doq disi / 初始化每点到初始化每点到A集合的最小集合的最小值值q inAi fal

16、se /设顶点不在设顶点不在A中中qdisr 0 /将将r设为设为0或或- ，预备，预备取出取出qfor i=1 to n doq v get-min() /取取dis?中最小的值中最小的值c和顶和顶点点v,q inA v true /v放入放入A中中q sum sum+c /c参与参与MST的总和中的总和中q updata( v ) /枚举交叉边枚举交叉边(v,B),改良改良dis 最小生成树(MST)-Prim算法q算法描画算法描画3：qMST_Kruskal(G)q (1)将将G一切条边按权从小到大排序；图一切条边按权从小到大排序；图mst开场开场为空为空q (2)从小到大次序取边从小到

17、大次序取边(x,y)q (3)假设参与边假设参与边(x,y)，mst就有环，那么放弃此就有环，那么放弃此边，转边，转(2)q (4)将边将边(x,y)参与参与mst，假设曾经加了，假设曾经加了n-1条边，条边，终了。否那么，转终了。否那么，转 (2)q算法证明：算法证明：q 根据剪切属性根据剪切属性 图图(?)最小生成树(MST)-Kruskal算法q算法要点：算法要点：q Kruskal算法的最难点在于怎样判别参与边算法的最难点在于怎样判别参与边(x,y)后能否构成了环。后能否构成了环。q问题可化为：问题可化为：q 判别边判别边(x,y)的两个顶点的两个顶点x,y在图实践是森在图实践是森林林

18、mst中最否曾经连通。假设曾经连通，参与中最否曾经连通。假设曾经连通，参与边将构成环；否那么，不构成环。边将构成环；否那么，不构成环。q 并查集：并查集：q 连通点集之类问题，有高效算法连通点集之类问题，有高效算法-并查集。并查集。最小生成树(MST)- Kruskal算法q并查集：并查集：q 并查集详细内容可参见有关文章。下面是并查集详细内容可参见有关文章。下面是Pascal段：段：q/初始化，使每个集合只一个元素。初始化，使每个集合只一个元素。q for i:=1 to n do f i :=i;q/查找查找x所在类的所在类的“根根-代表，并紧缩途径代表，并紧缩途径qfunction fi

19、nd_set(x:longint):longint; beginq if fxx then fx:=find_set(fx);q exit(fx);qend;q/合并两个集合。合并两个集合。x,y为两集合的为两集合的“根根qprocedure union(x,y:longint); beginq fx:=y;qend;最小生成树(MST)- Kruskal算法q并查集：并查集：q 并查集详细内容可参见有关文章。下面是并查集详细内容可参见有关文章。下面是C+片段：片段：q/初始化，使每个集合只一个元素。初始化，使每个集合只一个元素。q for (i=1;i = n ; i+) f i = i;q

20、/查找查找x所在类的所在类的“根根-代表，并紧缩途径代表，并紧缩途径qint find_set ( int x) q if (fx != x) fx = find_set( fx );q return (fx);qq/合并两个集合。合并两个集合。x,y为两集合的为两集合的“根根qvoid union(int x,y ) q fx = y;q最小生成树(MST)- Kruskal算法q算法描画算法描画4：qMST_Kruskal(G) qfor i=1 to n do fi i; /初始化并初始化并查集查集 qsort( e, e+m); /边按大小边按大小排序排序qc 0; /取边的计取边的计

21、数器数器qfor i=1 to m do /从小到大从小到大取边取边q v find_set( ei.v ); /左端点所左端点所在连通块在连通块“根根q u find_set( ei.u ); /右端点所右端点所在连通块在连通块“根根q if(v != u) /假设不在假设不在同一连通块同一连通块q union(v,u); /合并两连合并两连通块通块q sum += gvu; /参与这条参与这条边的权边的权q if (+c = n-1) break; /if 取了取了n-1条边，终了条边，终了最小生成树(MST)-Kruskal算法时间复杂度分析时间复杂度分析Prim算法普通的方法算法普通的

22、方法 O(|V|2) Prim算法中用算法中用“堆方法堆方法 O(|E|+|V|)*log|V|) -对稀疏图较对稀疏图较好好Kruskal算法算法 O(|E|*log|E| +|N|*A(|V|) -对稀疏图对稀疏图较好较好最小生成树(MST)-时间复杂度1 1、平面上有、平面上有N(=3000)N(=3000)个点，求连通它们个点，求连通它们的最小生成树，用什么算法比较好？的最小生成树，用什么算法比较好？2 2、要判别一条边能否可以在一棵、要判别一条边能否可以在一棵MSTMST上，上，怎样做比较好？怎样做比较好？3 3、平面上有、平面上有K K个水源井，个水源井，N N个居民供水个居民供水

23、点，怎样用最少的管道使这点，怎样用最少的管道使这N N个居民点都个居民点都能用衔接到水源。注：边只能水源、居民能用衔接到水源。注：边只能水源、居民点之间直接相连。点之间直接相连。最小生成树(MST)-思索题 maintain 有一个无向图，有N个点 ，有w条边。但是一开场，一切的边都是被破坏了的，即不可用。接下来每一天可以修复一条边。留意：两个点之间能够有多条边。 如今的问题是：每一天修复完一条边后，无向图中的恣意两个结点都可以连通了吗？假设还不可以输出-1，假设可以了，他从曾经修复的边中，选择一些边，使得这些边的总长度最小，输出最小值。最小生成树(MST)-实例二输入格式：输入格式：第一行第

24、一行: 两个整数：两个整数：N，W。 N (1=N=200) 、 W (1 = W e.c ，删除边，删除边x,参与边参与边e. M*N 1,200,000简化算法？简化算法？ 由于每次只保管由于每次只保管N-1条边，每次重新做条边，每次重新做Kruskal算算法：法：M*N*logN 9,600,000 大致可行。更可省略大致可行。更可省略排序，用插入法即可：排序，用插入法即可： M*N*3 = disy q q 松驰松驰q 假设在处置过程中，有两点假设在处置过程中，有两点x、y出现不符合出现不符合“三角形定理，那么可改良一下三角形定理，那么可改良一下松驰：松驰：q if ( disx+le

25、nxy =0,假设假设disv disx，那么，那么x永远不会松驰永远不会松驰v，故，故v点点确定下来。确定下来。最短途径-Dijkstra算法SXVdisvdisxA集合集合B集合集合n第一步，初始化第一步，初始化一切顶点一切顶点间隔置间隔置 源点源点置置 0 最短途径-Dijkstra算法n第二步，取出第二步，取出S，松驰相邻点，松驰相邻点松驰松驰S的相邻顶点的相邻顶点最短途径-Dijkstra算法源点源点红箭头表示方案前趋点红箭头表示方案前趋点S放入放入A集合集合取最近的顶点取最近的顶点x最短途径-Dijkstra算法n第三步第三步由对由对u松驰松驰由由x对对y松驰松驰最短途径-Dijk

26、stra算法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第八步第八步q算法描画算法描画2：qSP_Dijkstra(G, s) /求单源求单源s到其它点的最短到其它点的最短间隔间隔q for i=1 to n doq d

27、isi / 初始化每点到初始化每点到s间隔间隔q inAi false /设顶点不在设顶点不在A中中qdiss 0 /将将diss设为设为0，预备，预备取出取出qfor i=1 to n doq v get-min() /取取dis?中最小的值中最小的值c和顶点和顶点v,q inA v true /v放入放入A中中q sum sum+c /c参与参与MST的总和中的总和中q updata( v ) /检查检查(v,B),松驰松驰dis? 最短途径-Dijkstra算法与与prim不一不一样点样点cooking Bessie喜欢为在外面的奶牛做喜欢为在外面的奶牛做晚餐，晚餐，Bessie按响铃给

28、他们一个信按响铃给他们一个信号叫他们进来就可以了。号叫他们进来就可以了。 晚餐将在晚餐将在T (1 = T = 1,000,000)毫秒完成，而且毫秒完成，而且Bessie强调那些想吃她晚餐的奶牛必需准强调那些想吃她晚餐的奶牛必需准时到。时到。 这些牛在这些牛在F (1 = F = 500)各不各不同的草地标号为同的草地标号为1F用用P(1 = P = 10,000)个双向的小路衔接。个双向的小路衔接。 Bessie在第在第1个草地，个草地， 给出一给出一头牛走每一条小路所用的时间，问头牛走每一条小路所用的时间，问多少个草地上的奶牛可以在多少个草地上的奶牛可以在T毫秒毫秒内到内到Bessie

29、所在的草地，假设多所在的草地，假设多头牛可以共享一条路。头牛可以共享一条路。最短途径-实例一 假设边有负权的话，假设边有负权的话，Dijkstra算法是错误的。这算法是错误的。这里需求不断迭代地做里需求不断迭代地做“松驰，直到无松驰，直到无“松驰为松驰为止。止。算法描画算法描画3：SP_Bellman(G, s) (1)初始化每点到初始化每点到s点的最短间隔为点的最短间隔为 (2)取一切边取一切边(x,y)，看，看x能否对能否对y松驰。松驰。 (3)假设没有任何松驰，那么终了假设没有任何松驰，那么终了break。 (4)假设松驰次数假设松驰次数N，转，转(2) (5)否那么，图中有否那么，图中

30、有“负圈。负圈。最短途径-Bellman-ford算法算法阐明：算法阐明：Bellman-ford算法算法N次迭代就可以判别图中能否有次迭代就可以判别图中能否有“负环。负环。取一切边有两种方法：取一切边有两种方法： (1)扫描每一点的邻接链表扫描每一点的邻接链表 (2)用有序点对用有序点对(x,y)记录边时，可直接取边。但要记录边时，可直接取边。但要请留意对无向图，要留意请留意对无向图，要留意(y,x)也要松驰。也要松驰。对于求对于求s到某点到某点t的最短间隔，能够由于其它地方有的最短间隔，能够由于其它地方有“负环而出现问题，要预处置。负环而出现问题，要预处置。最短途径-Bellman-for

31、d算法q算法描画算法描画4：qSP_Bellman(G, s) /求单源求单源s到其它点的最短间隔到其它点的最短间隔q for i=1 to n doq disi / 初始化每点到初始化每点到s间隔间隔qdiss 0 /将将diss设为设为0qfor i=1 to n do /最多迭代最多迭代nq rel=false; /能否有松驰标志能否有松驰标志q for 每条边每条边(x,y) /取图的每一条边取图的每一条边q if( disx+lenxydisy) /不满足三角形性不满足三角形性质质q disy=disx+lenxy; /松驰松驰disyq rel=true;q if rel = fa

32、lse return 0; /没有一次松驰，没有一次松驰，那么终了那么终了qreturn -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组数据。组数据。多组数据测试每组数据：多组数据测试每组数据：第第1行：三个整数行：三个整数 N M W 第第2至至M+1行行:每行三个整数每行三个整数 (S, E, T)

34、,表示在表示在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行，每行对应一组数据，假设可以实现愿望输出行，每行对应一组数据，假设可以实现愿望输出YES,否那么输出否那么输出NO.最短途径-实例二输入样例输入样例(wormhole.in):23 3 11 2 21 3 42

35、 3 13 1 33 2 11 2 32 3 43 1 8最短途径-实例二输出样例输出样例(wormhole.out):NOYES 1233图图2481232413图图1分析分析 首先，把无向边改成两个有向边，这样整首先，把无向边改成两个有向边，这样整个问题成在有向图中求负环问题。个问题成在有向图中求负环问题。 N*(M+W) = 500*2500+2000) doq v qhead; /队头节点队头节点vq for 每条边每条边(v,i) /与与v相连的每一条边相连的每一条边q if( disv+lenvidisi) /不满足三角形性质不满足三角形性质q disi disv+lenvi; /

36、松驰松驰disiq if (visi = false) /不在队列，那么参不在队列，那么参与队列与队列q visi true; count+1;q tail+1; qtail = i;q visv false;head+1;count-1; /v出队列出队列最短途径- SPFA算法SPFA算法的思索算法的思索 对有向图，对有向图，s到到t的最短路问题依然有负环影响。的最短路问题依然有负环影响。无向图呢？无向图呢？怎样判别图上负环？怎样判别图上负环？ 最短途径-SPFA算法q求每对节点之间最短间隔问题：例如，求一求每对节点之间最短间隔问题：例如，求一个图的直径，即一切最短途径中最长的。个图的直径

37、，即一切最短途径中最长的。q 假设多次调用单源最短途径算法，效果并假设多次调用单源最短途径算法，效果并不好。特别是对有负边的图。不好。特别是对有负边的图。q假设无负环，那么有简单的假设无负环，那么有简单的Floyd-warshell算法。这是动态规划算法。算法。这是动态规划算法。最短途径-Floyd算法动态规划算法动态规划算法定义定义d i ,j , k 为为途径中间只允许经过节点途径中间只允许经过节点1k的情况下的情况下i到到j的最短路间隔的最短路间隔它有两种情况它有两种情况最短路经过点最短路经过点k，di,j,k=di,k,k-1+dk,j,k-1最短路不经过点最短路不经过点k，di,j,

38、k=di,j,k-1 综合起来，形状转移方程为综合起来，形状转移方程为 di,j,k=min di,k,k-1 + dk,j,k-1,di,j,k-1 边境条件边境条件 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放在最外层，放在最外层，数组少一维数组少一维 for i=1 to n do for j=1 to

39、 n do if( disi,k+diskjdisi,j) /形状转移形状转移 disi,j disik+diskj; 最短途径- Floyd算法Floyd算法的思索算法的思索Floyd算法怎样记录下最短途径？算法怎样记录下最短途径？Floyd算法怎样判别负环？算法怎样判别负环？求图中的最小环问题。求图中的最小环问题。最短途径-Floyd算法nDijkstran单源单源 非负非负 O(|V|2) 对稠密图好对稠密图好n可用可用“堆优化堆优化 O(|E|*log|V|) 对稀疏图较好对稀疏图较好nBellman-Fordn单源单源 无负环无负环 O(|V|*|E|)n可先用可先用Dijkstra

40、预处置优化预处置优化nSPFA用更新队列优化用更新队列优化,时间复杂度平均好，但不确定。时间复杂度平均好，但不确定。nFloydn全源全源 无负环无负环 O(|V|2)n思索：有多源问题类吗？思索：有多源问题类吗？n 假设边权只需假设边权只需0,1(或或0,1,2,3,4)，能否优化算法？，能否优化算法？最短途径-算法比较最短途径-实例三butter 农夫农夫John发现做出全威斯康辛州发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一最甜的黄油的方法：糖。把糖放在一片牧场上，他知道片牧场上，他知道N只奶牛会过来舔只奶牛会过来舔它，这样就能做出能卖好价钱的超甜它，这样就能做出能卖好价钱的超甜

41、黄油。黄油。 农夫农夫John可以训练这些奶牛，让可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。它们在听到铃声时去一个特定的牧场。他计划将糖放在那里然后下午发出铃他计划将糖放在那里然后下午发出铃声，以致他可以在晚上挤奶。声，以致他可以在晚上挤奶。 农夫农夫John知道每只奶牛都在各自知道每只奶牛都在各自喜欢的牧场一个牧场不一定只需一喜欢的牧场一个牧场不一定只需一头牛。给出各头牛所在的牧场和牧头牛。给出各头牛所在的牧场和牧场间的道路，找出使一切牛到达的路场间的道路，找出使一切牛到达的路程和最短的牧场他将把糖放在那程和最短的牧场他将把糖放在那最短途径-实例三输入格式输入格式 第一行第一行: 三个数，奶牛数三个数，奶牛数N1=N=500, 牧场数牧场数P2=P=800，牧场间道路数，牧场间道路数C (1=C=1450) 第二行到第第二行到第N+1行行: 1 到到 N 头奶牛所在的牧场头奶牛所在的牧场号号 第第N+2行到第行到第N+C+1行：行： 每行有三个数每行有三个数,相连相连的牧场的牧场A、B，两牧场间间隔，两牧场间间隔D1=D5*108要超时。要超时。 边比较少，可枚举每一点为源，再用边比较少，可枚举每一点为源，再用Dijkstra算法算法+堆优化来处置堆优化来处置: P*C*logP =800* 1450*log