图论 第二最短路

图论 第二最短路 图论算法总结 By:失落Dark 参加了省选的培训之后，我越发的了解到了图论算法的博大精深，其难度已远远超过我们这些小菜的水平，不过相对于NOIP难度的图论来说，难度并不大，现参照手上的一分资料对图论知识进行如下总结。 最小生成树:这算是最简单的图论算法之一了吧，常用的有Prim和Kruskal算法，对于Prim算法，它和求最短路径的O(N^2)算法Dijkstra是有相通之处的。Prim和Kruskal算法的时间效率相差不多，个人感觉Prim算法容易理解，可以视作涨水的模型来看，的却显得巧妙异常。(以USACO 3.1 Agri-Net 为例) 这道目是一个标准的最小生成树，不用任何转化或者优化，Prim算法思想就是不断找点，更新，再找点„.算法实现代码如下: //////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////// for i:=1 to n-1 do begin min:=maxlongint; for j:=1 to n do if (f[j]0) then begin min:=f[j]; k:=j; end; zong:=zong+min; f[k]:=0; for j:=1 to n do if f[j]>map[k,j] then f[j]:=map[k,j]; end; //////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////// 事实上，图论算法的代码都是相当死的，若不能理解，你完全可以将它记下来，做过更难的 图论算法后你才会发现，图论算法的精髓在于建图，而不是在于算法。 最短路径:最短路径是使用极为频繁的一种图论模型，其解题主要实现方式是松弛操作，即 是先将两点距离视为极大值，然后用其它点作中转进行优化，常见的算法有SPFA算法， Dijkstra算法以及Floyed算法，前两者的时间复杂度为O(N^2)，Floyed算法为O(N^3)，为 什么要把一个N^3的算法放在这里呢，因为其代码极为简洁，如果数据规模允许的情况下通 常采用Floyed算法，事实上，SPFA算法和Dijkstra算法是求单点的距离，Floyed算法求的 是任意两点距离，所以说Floyed的效率与这两者相比哪个更好还有待讨论啊。 因为spfa可以处理权值为负的情况，所以建议使用spfa算法，spfa算法的模块与宽搜(bfs) 的模块大致相似，也较容易理解: //////////////////////////////////////////////////////////////////////////////// ////////////////////////////////////////////////// l:=0;r:=1;line[r]:=a;h[a]:=true; repeat inc(l); h[line[l]]:=false; t:=line[l]; for i:=1 to n do begin if (i<>t)and(连接) then begin if 松弛 then begin 松弛 if h[i]=false then begin inc(r); line[r]:=i; h[i]:=true; end;end; end; end; until l>=r; 代码很简单的，至于代码的解释就引用资料上的一段话“我们用数组d记录每个结点的最短 路径估计值，而且用邻接

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

来存储图G。我们采取的

方法

快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载

是动态逼近法:设立一个先进先出 的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估 计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v 点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直 至队列空为止。 ” ，具体内容请自行揣摩。 第N短路算法:有了最短路算法，自然要有第N短路算法，虽然我不知道这在实际应用中有 什么用处，实际上这种变形是很好求解的: *第二最短路径:枚举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些 路径中最短的一条即为第二最短路径。 *同理，第n最短路径可在求解第n-1最短路径的基础上求解。 那么，怎样枚举最短路的每条边呢，可以想到如果F[1,N]=F[1,K]+F[K,N]，那么K点一定在 1到N的最短路上，那么重复枚举此过程，就可以求得每一条边，然后再根据上面的步骤求 解第N短路即可。代码就不给了。 最大匹配和最优匹配:最大匹配和最优匹配实际上在NOIP里并不常考，这么多年似乎也没考 过，但是我们还是要做好准备，以防他出偏题，最大匹配和最优匹配实际上都是可以用网络 流来求解的，但专用于解决这两种问题的“匈牙利算法”和“KM算法”要比网络流简单得多， 所以学习这两种算法来应对NOIP已经足够了。 匈牙利算法仔细一想，还是很容易理解的，我的同学还有自行贪心“贪”出匈牙利算法的呢， 我们来看代码解释吧: function find(x:longint):boolean; var k,i,j:longint; begin for j:=1 to m do if (line[x,j])and(not used[j]) then begin used[j]:=true; if (aim[j]=0) or(find(aim[j])) then begin aim[j]:=x; exit(true); end; end; exit(false); end; //////////////////////////////////////////////////////////////////// 1. 首先j枚举所有 2. used这个数组的作用就是用来标记这个点是否还可用，比如说A只能找B，而B已经有了C，那就可以给C重新找一个对象，那么自然不能再找B了，这样才能配出最大匹配。 3. aim数组是用来储存这个点的目标点的。 4. (aim[j]=0) or(find(aim[j]))这一句的意思就是如果j没有对象，或者还可以另找一个对象，那么就执行以下程序。 ///////////////////////////////////////////////////////////////////// 至于最大匹配的KM算法，解释起来更加麻烦，我们学的时候都讲了几节课，我水平不够，就不在这里浪费口水了吧。匈牙利算法的难点主要是如何建图，这个就..