最短路算法及其应用(4)

2006年全国信息学冬令营讲座

解决这个问题。例如图5，若m=2，则将两台设备分别用于1-3，3-5的线路，传输用时可减少为22秒，这是最佳解。

2 10 24 3 20 5 12 16 4 34 1 30 图5

输入格式

从文件network.in输入。第一行先输入n,m。以下n行，每行有n个实数。第i行第j列的数为计算机i与计算机j之间网线的传输用时，0表示它们之间没有网线连接。注意输入数据中，从计算机1到计算机n至少有一条网路。 输出格式

输出到文件network.out。输出计算机1与计算机n之间传输信息的最短时间。同时输出m台设备分别用于何处。 样例输入

network.in 5 2

0 34 24 0 0 34 0 10 12 0 24 10 0 16 20 0 12 16 0 30 0 0 20 30 0 样例输出

network.out 22.00 1 3 3 5 分析：

题目中背景过多，让我们重新描述一下问题：

给定含有n个顶点的带权无向图，一共可以进行m次操作，每次操作将一条边的权值除以2。问每次应该对哪条边进行操作，使得1到n的最短路径权和最小。

如果我们把Dijkstra算法直接用在原图上，得到的是没有使用任何加速设备顶点1到顶点n的最短路长，不是我们想要的结果。

能否用增量法做这题呢？就是，我们先求出使用前m-1台加速设备的最短路长，然后通过枚举之类算出第m台设备用在那条边上，行不行呢？

经过简单的举例后发现行不通。 一个明显的反例是：

第16页

2006年全国信息学冬令营讲座

2 16 1 1 40 3 8 4 图6

如果我们只有一个加速设备的话，显然将它加在1-2上，那么最短路长16是最佳的。但是，我们有两个的话，将两个都加在3-4上，则最短路长11是最优的。

所以要是我们的加速设备增多一台的话，可能导致前面的所有放置方案都不是最优值。

让我们回忆一番学过的各种算法，看看能否有所帮助。

搜索？无论剪枝条件有多强，算法的复杂度始终是指数级别的??行不通；

数学方法？我们发现方案具有很大的随意性，同构但是权值不同的图答案可能完全不同，加速设备台数的不同也可能导致方案完全不同??数学方法也行不通；

贪心？刚才用的增量法其实应该属于贪心范畴的，很明显可以看出，局部的最优与全局最优有相当大的差别，所以估计其他策略的贪心也起不到什么作用??同样行不通；

动态规划？动态规划的两个基本要素是：状态的表示以及状态的转移。我们会发现在状态的表示上我们就遇到了困难。如果仅将点和设备台数作为元素，边的权值改变了，方程上必须体现出来，这似乎很难操作。如果加上边作为元素，一者空间上不能承受，二者撇开空间，这时候的效率和盲目搜索已经没有太大差别了。

以往学过的知识对于解题似乎毫无裨益。 为什么？

我们刚才犯了一个挺严重的错误，就是脱离了题目来想算法。这好比建空中楼阁，失败是难免的。

回到题目上。我们注意到一点，就是n和m都很小，特别是m，最大只有10。直觉和经验告诉我们，应该从数据规模小上面作文章。

从简单情形入手往往也是解题的捷径。

没有m值，或者说m=0时，问题的解就是最简单的最短路径问题。m值的出现导致了最短路算法的失败。

关键是我们不知道应该在哪几条边用加速设备，而且每条边用多少次也不知道。方案与权值的分布还有m值的大小都有莫大的关联。

我们想想，有无m值的差异在哪，能够消除吗？

可以的。构造图G=(V,E)。设原图V0={v1，v2，??，vn}，将原图中的每个顶点vi拆成m+1个顶点vi,0，vi,1，vi,2，??，vi,m构造V使得

V={vi,0，vi,1，vi,2，??，vi,m|vi?V0}

对于原图的每一条边，注意是无向的，ek=vivj?E0，将它拆成(m+1)(m+2)

第17页

2006年全国信息学冬令营讲座

条有向边(ek)0,0=vi,0vj,0，(ek)0,1=vi,0vj,1，??，(ek)m,m=vi,mvj,m，(ek)'0,0=vj,0vi,0，(ek)'0,1=vj,0vi,1，??(ek)'m,m=vj,mvi,m。构造E使得

E={(ek)p,q=vi,pvj,q，(ek)'p,q=vj,pui,q|ek=vivj?E0,0<=p<=q<=m}

最后设定权函数w。对于vi,pvj,q?E，w满足：

w(vi,pvj,q)=w(vivj)×2q-p 解释一下图G的含义。

为了更清楚地说明问题，我们举出一个例子。图7(a)显示了某个G0(n=2,m=2)，按照以上的构造方法得出图7(b)中的G。将图G分成三层，第0层由顶点v1,0，v2,0构成，第1层由顶点v1,1，v2,1构成，第2层由顶点v1,2，v2,2构成。可以看出，若两个顶点间有边相连，两个顶点在同一层的，则顶点之间是互连的，若不在同一层，则层号小的顶点为边的起始点，层号大的为边的终点。

1,0 2 1 8 2 1,1 4 8 2,2 4 8 4 2 8 4 2,1 2,0 1,2 (a) (b) 图7

层号代表已用的加速设备台数，例如从v1,0到v2,1需要且恰好要用一台加速设备。我们无法从层号大的顶点到达层号小的顶点，这符合同一个设备不能使用多次的规定。

剩下的工作就是对图G使用Dijkstra算法求v1,0到vn,m的最短路长。相信大家都会，我就不多说了。

最短路长就是添置m台加速设备后计算机1到计算机n的最少传输时间。

四、总结

本文首先介绍了最短路的一些相关概念，它们是后边介绍的三种算法的基础。其中的某些性质对于建立最短路模型十分有用。

Dijkstra算法的效率高，但是也有局限性，就是对于含负权的图无能为力。 Bellman-Ford算法对于所有最短路长存在的图都适用，但是效率常常不尽人意。

SPFA算法可以说是综合了上述两者的优点。它的效率同样很不错，而且对于最短路长存在的图都适用，无论是否存在负权。它的编程复杂度也很低，是性价比极高的算法。

在不含负权的图中，特别是在边数稠密的图中，我们常常选择Dijkstra算

第18页

2006年全国信息学冬令营讲座

法，在稀疏图中，二叉堆实现的Dijkstra算法也是不错的选择，SPFA算法效率极高；图中含有负权，稀疏图随便用后两种算法中的那一种都行，因为它们的效率都可以接受，而且都很容易写，要是稠密图的话，就非SPFA莫属了。总之，我们应该根据实际需要，找到时空复杂度和编程复杂度的平衡点，在考场上用最少的时间拿尽可能多的分数。

对于绝大多数最短路问题，我们只需套用经典算法就行了。所以往往我们的难点是在模型的建立上。

这要求我们对最短路的核心思想有较深入的了解，对题目的本质有较全面的认识，还需要丰富的解题经验，??这里是最考察一个人综合素质的地方。

实际中遇到的题目可能千奇百怪，模型的转化千变万化，从而导致解法也多种多样，不拘一格，本文实在难以涵盖万一，只要能对读者有所启发，那么我的目的也就达到了。

最后送上两句话： 万变不离其宗。

——把握最短路的核心思想，合理转化模型。 阵而后战，兵法之常；运用之妙，存乎一心。 ——因地制宜，根据实际选择最合适的算法。

【感谢】

感谢黄叶亭老师对我的指导，提出宝贵的意见和指出论文的不足之处。 感谢邹雨晗、江弘升同学在写论文的过程中所给予的帮助。

【参考文献】

一、《实用算法分析和程序设计》 吴文虎 王建德 电子工业出版社 二、《算法艺术与信息学竞赛》 刘汝佳 黄亮 清华大学出版社 三、《金牌之路·高中计算机》 王建德 周咏基 陕西师大出版社 四、《Introduction to Algorithm》 Thomas H.Cormen等 The MIT Press

【附录】

附录一：例题一 货币兑换 英文原题

Currency Exchange Time Limit: 1.0 second Memory Limit: 1 000 KB

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency.

第19页

2006年全国信息学冬令营讲座

For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 - 0.39) * 29.75 = 2963.3975RUR.

You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B - numbers of currencies it exchanges, and real RAB, CAB, RBA and CBA - exchange rates and commissions when exchanging A to B and B to A respectively.

Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations.

Input

The first line of the input file contains four numbers: N - the number of currencies, M - the number of exchange points, S - the number of currency Nick has and V - the quantity of currency units he has. The following M lines contain 6 numbers each - the description of the corresponding exchange point - in specified above order. Numbers are separated by one or more spaces. 1 <= S <= N <= 100, 1 <= M <= 100, V is real number, 0 <= V <= 103.

For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10-2 <= rate <= 102, 0 <= commission <= 102.

Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence. You may assume that ratio of the numeric values of the sums at the end and at the beginning of any simple sequence of the exchange operations will be less than 104.

Output

If Nick can increase his wealth, output YES, in other case output NO to the output file.

Sample Input 3 2 1 20.0

1 2 1.00 1.00 1.00 1.00 2 3 1.10 1.00 1.10 1.00 Sample Output YES

附录二： 例题二 双调路径 英文原题

Bicriterial routing

第20页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库最短路算法及其应用(4)在线全文阅读。