最短路模型构建与求解

最短路模型构建与求解方法湖南省长沙市第一中学曹利国问题原型一：单源最短路用带权的有向图表示一个交通运输网，图中：顶点——表示城市边——表示城市间的交通联系权——表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径516432085623013717329长度最短路径<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4>21<V0,V2,V3,V4,V5><V0,V1,V6>138131920首先把V分成两组：（1）S：

已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合然后将T中顶点按最短路径递增的次序加入到S中，保证：

（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的最短路径长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最

短路径长度原型求解方法迪杰斯特拉(Dijkstra)算法算法思想：按路径长度递增次序产生最短路径的算法。依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。初使时令S={V0},T={其余顶点}，T中顶点对应的距离值若存在<V0,Vi>，为<V0,Vi>弧上的权值若不存在<V0,Vi>，为

从T中选取一个其距离值为最小的顶点W，加入S对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值重复上述步骤，直到S中包含所有顶点，即S=V为止Dijstra算法求最短路径具体步骤516432085623013717329实例演示终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj13<V0,V1>8<V0,V2>

30<V0,V4>

32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>

32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>问题原型二：任意顶点对之间的最短路径求解方法方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次---T(n)=O(n³)方法二：弗洛伊德(Floyd)算法算法思想：逐个顶点试探法求最短路径步骤初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为

逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值所有顶点试探完毕，算法结束实例演示ACB264311041160230初始：路径：ABACBABCCA0411602370加入A：路径：ABACBABCCACAB046602370加入B：路径：ABABCBABCCACAB046502370加入C：路径：ABABCBCABCCACAB模型构建方法与问题分析问题A：渡河问题

一个人带了一只狼、一只兔子和一棵白菜想要过河。河上有一只独木船，每次除了人以外，只能带一样东西。另外如果人不在旁时狼就要吃兔子，兔子就要吃白菜。问应该怎样安排过河，才能做到既把所有东西都带过河，在河上来回的次数又最少？模型构建：问题A最短路模型的建立图的顶点对于左岸的情况，我们可以用集合表示。这样一共会有24=16种状态：[人、狼、兔、菜][人、狼、兔] [人、狼、菜][人、兔、菜][狼、兔、菜]

[人、狼][人、兔][人、菜][狼、兔][狼、菜][兔、菜]

[人][狼][兔][菜][]其中有狼吃兔、兔吃菜的情况的有：[狼、兔、菜]，[人、狼]，[人、菜]，[狼、兔]，[兔、菜]，[人]这6种情况，将他们删掉，就剩下10个集合了。将这10个集合看成我们的图中的10个顶点。图的边与权这10个顶点，若是一个顶点的情况可以通过一次渡河得到另一个顶点的情况，就在这两个顶点之间连一条权值为1的无向边。这样，图论模型就建立了。问题就转化成了求[人、狼、兔、菜]到[]的最短路径。模型求解问题B：最优乘车（NOI97）

H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士,这样换乘几次后到达S公园。现在用整数1，2，……N给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1，公园巴士站的编号为N。写一个程序，帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程中换车的次数最少。模型构建由于同一线路中不需要换车67473621356747362135样例数据对应图添加边后构成的图1234567模型求解将相同点合并后得到的有向图有向图中的边的权值为1，问题转化为：求起点1到终点n的最短路。假设最短路长为m。由于坐车耗费在每条线路上的代价都是1，而不同线路间是通过同一站联系的，所以换线路并不耗时，因此m即表示从起点1到终点n所经过的最少线路数。而最少换车次数即等于经过的最少线路数减一。问题C：求解《01串问题》（NOI99）给定7个整数N,A0,B0,L0,A1,B1,L1，要求设计一个01串S=s1s2…si…sN，满足：（1）si=0或si=1，1<=i<=N；（2）对于S的任何连续的长度为L0的子串sjsj+1…sj+L0-1(1<=j<=N-L0+1)，0的个数大于等于A0且小于等于B0;（3）对于S的任何连续的长度为L1的子串sjsj+1…sj+L1-1(1<=j<=N-L1+1)，1的个数大于等于A1且小于等于B1;例如，N=6,A0=1,B0=2,L0=3,A1=1,B1=1,L1=2，则存在一个满足上述所有条件的01串S=010101。输入：仅一行，有7个整数，依次表示N,A0,B0,L0,A1,B1,L1（3<=N<=1000，1<=A0<=B0<=L0<=N，1<=A1<=B1<=L1<=N），相邻两个整数之间用一个空格分隔。输出：仅一行，若不存在满足所有条件的01串，则输出一个整数-1，否则输出一个满足所有条件的01串。样例输入6123112样例输出010101模型构建图的顶点

用Ci表示s1,s2….si中1的个数，我们可以得到C1,C2….Cn，用他们作图的顶点，将C0也考虑进去（显然：C0=0），我们就得到了N+1个顶点。图的边与权若我们已找到一个串S，则这个串S必须满足如下性质：对任意的i，一定符合下面的不等式：于是，根据这些不等式，我们得到了点与点之间的关系。按照这些不等式中大于等于符号的方向连接有向边，用加号后面的值作为边的权值，我们就可以构建出一个图论模型。模型求解<1>判断是否有解这时前面构建的图论模型可以发挥很大的作用。考虑这样一种情况：若x+y+z<0则Ci

<Ci这种情况显然是不可能得到的，若是出现了这种情况，则说明问题无解。其实这种情况就是构建的图中出现负权回路的情况！<2>求出S序列要求出S序列，我们只要求出C数组就可以了。因为C数组和S序列是一一对应的关系。而C数组的值，又可以通过构建的图论模型来求解。图中C0节点到各个节点的最短距离，就是各个节点的值。<3>算法从前两点得知，我们需要完成两件工作：第一件就是判断图中是否有负权回路；第二件就是求C0到各个节点的最短距离。要解决这两件事情，我们可以选择Bellman-Ford算法。<4>算法改进通过分析Bellman-Ford算法的本质，我们可以在它的基础上得到一个更简单的迭代算法：1）每一轮更新依次访问C0到Cn。每次访问到节点Ci，根据前面推出的6个不等式，更新另外6个节点的值。2）重复1）步骤，直到无法更新或更新的轮数大于2n为止。

若更新的轮数大于2n，则说明有负权回路，问题无解；若更新的轮数小于等