搜档网
当前位置:搜档网 › 最短路算法及其应用

最短路算法及其应用

最短路算法及其应用
最短路算法及其应用

最短路算法及其应用

广东北江中学余远铭【摘要】

最短路问题是图论中的核心问题之一,它是许多更深层算法的基础。同时,该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系,却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围,并对其应用做出了举例说明,侧重于模型的建立、思考和证明的过程,最后作出总结。

【关键字】

最短路

【目录】

一、基本概念 (2)

1.1 定义 (2)

1.2简单变体 (2)

1.3负权边 (3)

1.4重要性质及松弛技术 (4)

二、常用算法 (5)

2.1 Dijkstra算法 (5)

2.2 Bellman-Ford算法 (7)

2.3 SPFA算法 (8)

三、应用举例 (10)

3.1 例题1——货币兑换 (10)

3.2 例题2——双调路径 (11)

3.3 例题3——Layout (13)

3.4 例题4——网络提速 (15)

四、总结 (18)

【正文】

一、基本概念

1.1 定义

乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并

在地图上标出了每对十字路口之间的距离,如何找出这一最短行程?

一种可能的方法是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。然而我们很容易看到,即使不考虑含回路的路径,依然存在数以百万计的行车路线,而其中绝大多数是没必要考虑的。

下面我们将阐明如何有效地解决这类问题。在最短路问题中,给出的是一

有向加权图G=(V ,E),在其上定义的加权函数W:E →R 为从边到实型权值的映射。路径P=(v 0, v 1,……, v k )的权是指其组成边的所有权值之和:

11()(,)k

i i i w p w v

v -==∑

定义u 到v 间最短路径的权为

{}{}m in ():)w p u v u v v δυ→(,=∞ 如果存在由到的通路

如果不存在

从结点u 到结点v 的最短路径定义为权())w p v δυ=(,的任何路径。

在乘车旅行的例子中,我们可以把公路地图模型化为一个图:结点表示路口,边表示连接两个路口的公路,边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。

边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用来表示

时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。

1.2简单变体

单目标最短路径问题: 找出从每一结点v 到某指定结点u 的一条最短路

径。把图中的每条边反向,我们就可以把这一问题转化为单源最短路径问题。

单对结点间的最短路径问题:对于某给定结点u 和v ,找出从u 到v 的一

条最短路径。如果我们解决了源结点为u 的单源问题,则这一问题也就获得了解决。对于该问题的最坏情况,从渐进意义上看,目前还未发现比最好的单源算法更快的方法。

每对结点间的最短路径问题:对于每对结点u 和v ,找出从u 到v 的最短

路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。

1.3负权边

在某些单源最短路问题中,可能存在权为负的边。如果图G(V ,E)不包含由

源s 可达的负权回路,则对所有s v V ∈,最短路径的权的定义(,)s v δ依然正确。

即使它是一个负值也是如此。但如果存在一从s 可达的负权回路,最短路径的定义就不能成立了。从s 到该回路上的结点不存在最短路径——因为我们总可以顺着找出的“最短”路径再穿过负权回路从而获得一权值更小的路径,因此如果从s 到v 的某路径中存在一负权回路,我们定义(,)s v δ=-∞。

图1 含有负权和负权回路的图

图1说明负的权值对最短路径的权的影响。每个结点内的数字是从源点s

到该结点的最短路径的权。因为从s 到a 只存在一条路径(路径),所以:(,)(,)3s a w s a δ==。 类似地,从s 到b 也只有一条通路,所以:

(,)(,)(,)3(4)1s b w s a w a b δ=+=+-=-。

从s 到c 则存在无数条路径:,,等等。因为回

的权为6+(-3)=3>0,所以从s 到c 的最短路径为,其权为:

(,)5s c δ=。

类似地,从s 到d 的最短路径为,其权为:

(,)(,)(,)11s d w s c w c d δ=+=。

同样,从s 到e 存在无数条路径:,,等等.由于回

的权为3+(-6)=-3<0,所以从s 到e 没有最短路径。只要穿越负权回路任意次,我们就可以发现从s 到e 的路径可以有任意小的负权值,所以:

(,)s e δ=-∞

类似地,

(,)s f δ=-∞

因为g 是从f 可达的结点,我们从s 到g 的路径可以有任意小的负权值,

则:

(,)s g δ=-∞。

结点h ,j ,i 也形成一权值为负的回路,但因为它们从s 不可达,因此

(,)(,)(,)s h s i s j δδδ===∞。

一些最短路径的算法,例如Dijkstra 算法,都假定输入图中所有边的权取

非负数,如公路地图实例。另外一些最短路算法,如Bellman-Ford 算法,允许输入图中存在权为负的边,只要不存在从源点可达的权为负的回路,这些算法都能给出正确的解答。特定地说,如果存在这样一个权为负的回路,这些算法可以检测出这种回路的存在。

1.4重要性质及松弛技术

本文的算法所运用的主要技术是松弛技术,它反复减小每个结点的实际最

短路径的权的上限,直到该上限等于最短路径的权。让我们看看如何运用松弛技术并正式证明它的一些特性。

定理1 (最优子结构) 给定有向加权图G=(V ,E),设P=为从结

点v 1到结点v k 的一条最短路径,对任意i,j 有i<=j<=k ,设P ij =< v i , v i+1,…, v j >为从v i 到v j 的P 的子路径,则P ij 是从v i 到v j 的一条最短路径。

证明:我们把路径P 分解为。则

w(P)=w(P 1i )+w(P ij )+w(P jk )。现在假设从v i 到v j 存在一路径P ’ij ,且w(P ’ij )

下面看定理1的一个推论,它给出了最短路径的一个简单而实用的性质:

推论1.1 给定有向加权图G=(V ,E),源点为s ,则对于所有边(u,v)?E ,有

(,)(,)(,)s v s u w u v δδ≤+

证明: 从源点s 到结点v 的最短路径P 的权不大于从s 到v 的其它路径的

权。特别地,路径P 的权也不大于某特定路径的权,该特定路径为从s 到u 的最短路径加上边(u,v)。(证毕)

下面介绍松弛技术。

对每个结点v ∈V ,我们设置一属性d[v]来描述从源s 到v 的最短路径的权

的上界,称之为最短路径估计。我们通过下面的过程对最短路径估计和先辈初始化。

经过初始化以后,对所有v ∈V ,π[v]=NIL ,对v=s ,d[v]=0,对v ∈V-{s},

INITIALIZE-SINGLE-SOURCE(G ,s) 1. For 每个结点 v ∈V[G] 2. Do d[v]←∞ 3. π[v]←NIL 4. d[s]←0

d[v]= ∞。

松弛一条边(u,v)的过程包括测试我们是否可能通过结点u对目前找出的到v的最短路径进行改进,如果可能则更新d[v]和π[v],一次松弛操作可以减小最短路径的估计值d[v]并更新v的先辈域π[v],下面的代码实现了对边(u,v)的进一步松弛操作。

RELAX(u,v,w)

1.If d[v]>d[u]+w(u,v)

2.Then d[v]←d[u]+w(u,v)

3.π[v]←u

图2 对边(u,v)进行松弛

图2说明了松弛一条边的两个实例,在其中一个例子中最短路径估计减小,而在另一实例中最短路径估计不变。(a)因为在进行松弛以前d[v]>d[u]+w[u,v],所以d[v]的值减小。(b)因为松弛前d[v]<=d[u]+w[u,v],所以松弛不改变d[v]得值。

下文介绍的每个算法都调用INITIALIZE-SINGLE-SOURCE,然后重复对边进行松弛的过程RELAX。区别在于对每条边进行松弛操作的次数以及对边执行操作的次序有所不同。需要指出的是,松弛是改变最短路径估计和先辈的唯一方式。

二、常用算法

这一节着重讨论两种常用算法:Dijkstra算法和Bellman-Ford算法。虽然它们都是建立在松弛技术基础上的算法,但是在实现上有着各自的特点,适用的范围也有所不同。

另外,我们还将介绍一种期望复杂度与边数同阶的高效算法——SPFA算法,并对其复杂度作出简要的分析。

2.1 Dijkstra算法

Dijkstra算法解决了有向加权图的最短路径问题,该算法的条件是该图所有边的权值非负,因此在本小节我们约定:对于每条边(u,v)∈E,w(u,v)>=0。

Dijkstra算法中设置了一结点集合S,从源结点s到集合S中结点的最终最短路径的权均已确定,即对所有结点v∈S,有d[v]=δ(s,v)。算法反复挑选出其最短路径估计为最小的结点u∈V-S,把u插入集合S中,并对离开u 的所有边

进行松弛。在下列算法实现中设置了优先队列Q,该队列包含所有属于V-S的结点,且队列中各结点都有相应的d值。算法假定图G由临接表表示。

Dijkstra(G,w,s)

1.INITIALIZE-SINGLE-SOURCE(G,S)

2.S←?

3.Q←V[G]

4.While Q≠?

5.Do u←EXTRACT-MIN(Q)

6.S←S U{u}

7.For 每个顶点v∈Adj[u]

8.Do RELAX(u,v,w)

Dijkstra算法如图3所示对边进行松弛操作,最左结点为源结点,每个结点内为其最短路径估计。

图3 Dijkstra算法的执行流程

阴影覆盖的边说明了前驱的值:如果边(u,v)为阴影所覆盖,则π[v]=u。黑色结点属于集合S,白色结点属于优先队列Q=V-S。第1行对d和π值进行通常的初始化工作。第2行置集合S为空集。第3行对优先队列Q进行初始化使其包含V-S=V-?=V中的所有结点。每次执行第4-8行的While循环时,均从队列Q=V-S中压出一结点u并插入到集合S中(第一次循环时u=s)。因此在V-S中的所有结点中,结点u具有最小的最短路径估计。然后,第7-8行对以u为起点的每条边(u,v)进行松弛。如果可以经过u来改进到结点v的最短路径,就对估计值d[v]以及先辈π[v]进行更新。注意在第3行以后就不会再插入结点到Q中,并且每个结点只能从Q弹出并插入S一次,因此第4至8行的While循环的迭代次数为|V|次。

因为Dijkstra算法总是在集合V-S中选择“最轻”或“最近”的结点插入集合S中,因此我们说它使用了贪心策略。需要指出的是,贪心策略并非总能获得全局意义上的最理想结果。但Dijkstra算法确实计算出了最短路径,关键是要证明:

定理2 每当结点u插入集合S时,有d[u]=δ(s,u)成立。

简证:我们每次选择在集合V-S中具有最小最短路径估计的结点u,因为我们约定所有的边权值非负,所以有可能对结点u进行松弛操作的结点必不在集合V-S中(否则与结点u的定义矛盾),因此只会在集合S中。又由于我们选取结点进入S时,S中的结点已全部进行过松弛操作了,所以d[u]的值不会再发生改变。因此d[u]=δ(s,u)。(证毕)

我们最关注的问题是:Dijkstra算法的执行速度如何?首先我们考虑用一维数组来实现优先队列Q=V-S的情形。在该算法的实现下,每次EXTRACT-MIN 操作运行时间为O(V),存在|V|次这样的操作,所以EXTRACT-MIN的全部运行时间为O(V2)。因为每个结点v∈V仅被插入集合S一次,所以在算法的执行过程中邻接边Adj[v]中的每条边在第4-8行的For循环中仅被考察一次。因为在所有邻接表中边的总数为|E|,所以在该For循环中总共存在|E|次迭代,每次迭代运行时间为O(1),因此整个算法的运行时间为O(V2+E)=O(V2)。

但在稀疏图的情形下,用二叉堆来实现优先队列Q是比较实用的。在该算法实现下,每个EXTRACT-MIN操作需要时间为O(lgV),存在|V|次这样的操作。建立二叉堆需要时间为O(V)。在RELAX中的赋值语句d[v]←d[u]+w(u,v)是通过调整结点v在二叉堆中的位置来完成的,运行时间为O(lgV),并且至多存在|E|次这样的操作。因此算法的全部运行时间为O((V+E)lgV)。通常情况下,边数|E|都不小于结点数|V|,所以运行时间又可以简化为O(ElgV)。

用Fibonacci堆来实现优先队列Q的话,可以将运行时间改为O(VlgV+E)。|V|次EXTRACT-MIN操作中每次的平摊代价为O(lgV),且|E|次RELAX中调整结点v位置每次的平摊时间仅为O(1)。

事实上,Fibonacci堆的实现相当繁琐,在竞赛有限的时间里基本上不大可能写出来并调试好。另外,Fibonacci堆算法中隐含的系数相当大,程序的实际运行效果并不理想。目前该堆的理论价值远大于实用价值。因此,我们不推荐在分秒必争的竞赛中使用。

顺便说一句,Dijkstra算法和宽度优先搜索以及计算最小生成树的Prim算法都有类似之处。

2.2 Bellman-Ford算法

Bellman-Ford算法能在更一般的情况下解决单源点最短路径问题,在该算法下边的权可以为负。正如Dijkstra算法一样,Bellman-Ford算法运用了松弛技术,对每一结点v∈V,逐步减小从源s到v的最短路径的估计值d[v]直至其达到实际最短路径的权δ(s,v),如果图中存在负权回路,算法将会报告最短路不存在。

Bellman-Ford(G,w,s)

1.INITIALIZE-SINGLE-SOURCE(G,s)

2.For i←1 to |V[G]|-1

3.Do For 每条边(u,v)∈E[G]

4.Do RELAX(u,v,w)

5.For每条边(u,v)∈E[G]

6.Do If d[v] > d[u] + w(u, v)

7.Then Return FALSE

8.Return TRUE

源结点为z。每个结点内为该结点的d值,阴影覆盖的边说明了 值。在该实例中,Bellman-Ford算法返回TRUE。在进行了通常的初始化后,算法对图的边执行|V|-1次操作。每次均为第2-4行For循环的一次迭代,在迭代过程中对图的每条边松弛一次,图4(b)-(c)说明了全部四次操作的每一次后算法的状态,在进行完|V|-1次操作后,算法5-8行检查是否存在负权的回路并返回正确的布尔值。

Bellman-Ford算法的运行时间为O(VE)。因为第1行的初始化占用时间为O(V),第2-4行对边进行的|V|-1次操作的每一次运行时间为O(E),第5-7行的For循环的运行时间为O(E)。

图4 Bellman-Ford算法的执行流程

Bellman-Ford算法的思想基于以下事实:“两点间如果有最短路,那么每个结点最多经过一次。也就是说,这条路不超过n-1条边。”(如果一个结点经过了两次,那么我们走了一个圈。如果这个圈的权为正,显然不划算;如果是负圈,那么最短路不存在;如果是零圈,去掉不影响最优值)

根据最短路的最优子结构(定理1),路径边数上限为k时的最短路可以由边数上限为k-1时的最短路“加一条边”来求,而根据刚才的结论,最多只需要迭代n-1次就可以求出最短路。

这里介绍一个优化。很多时候,我们的算法并不需要运行|V|-1次就能得到最优值了,这之后的运行就是浪费时间。因此,对于一次完整的第3-4行操作,要是一个结点的最短路径估计值也没能更新,就可以退出了(因为既然当前这次都不能更新,下一次肯定也不能)。这个简单而显然的优化能大大提高程序的运行速度。虽然优化后的最坏情况依然是O(VE),但是对于多数情况而言,程序的实际运行效率将远离O(VE)而变为O(kE),其中k是一个比|V|小很多的数。

目前,对Bellman-Ford的进一步优化尚在不断研究中。

2.3 SPFA算法

求单源最短路的SPF A算法的全称是:Shortest Path Faster Algorithm。

从名字我们就可以看出,这种算法在效率上一定有过人之处。

很多时候,给定的图存在负权边,这时类似Dijkstra 等算法便没有了用武

之地,而Bellman-Ford 算法的复杂度又过高,SPF A 算法便派上用场了。

简洁起见,我们约定有向加权图G 不存在负权回路,即最短路径一定存在。

当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点。

和上文一样,我们用数组d 记录每个结点的最短路径估计值,而且用邻接

表来存储图G 。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u ,并且用u 点当前的最短路径估计值对离开u 点所指向的结点v 进行松弛操作,如果v 点的最短路径估计值有所调整,且v 点不在当前的队列中,就将v 点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。

定理3 只要最短路径存在,上述SPFA 算法必定能求出最小值。

证明:每次将点放入队尾,都是经过松弛操作达到的。换言之,每次的优

化将会有某个点v 的最短路径估计值d[v ]变小。所以算法的执行会使d 越来越小。由于我们假定图中不存在负权回路,所以每个结点都有最短路径值。因此,算法不会无限执行下去,随着d 值的逐渐变小,直到到达最短路径值时,算法结束,这时的最短路径估计值就是对应结点的最短路径值。(证毕)

刚才我们只是笼统地说SPF A 算法在效率上有过人之处,那么到底它的复

杂度是怎样的?

定理4 在平均情况下,SPFA 算法的期望时间复杂度为O(E)。

证明:上述算法每次取出队首结点u ,并访问u 的所有临结点的复杂度为

O(d),其中d 为点u 的出度。运用均摊分析的思想,对于|V|个点|E|条边的图,点的平均出度为E

V ,所以每处理一个点的复杂度为O(E V )。假设结点入队的次数

h ,显然h 随图的不同而不同。但它仅与边的权值分布有关。我们设h=kV ,则算法SPF A 的时间复杂度为()E h T O h O E O kE V V ????=?

=?= ? ??

???。在平均的情况下,SPFA (G ,w,s) 1. INITIALIZE-SINGLE-SOURCE(G ,s) 2. INITIALIZE-QUEUE(Q) 3. ENQUEUE(Q,s) 4. While Not EMPTY(Q) 5. Do u ←DLQUEUE(Q) 6. For 每条边(u,v)∈E[G] 7. D o tmp ←d[v] 8. Relax(u,v,w) 9. If (d[v] < tmp) and (v 不在Q 中) 10. ENQUEUE(Q,v)

可以将k看成一个比较小的常数,所以SPF A算法在一般情况下的时间复杂度为O(E)。(证毕)

聪明的读者一定发现了,SPF A和经过简单优化的Bellman-Ford无论在思想上还是在复杂度上都有相似之处。确实如此。两者的思想都属于标号修正的范畴。算法是迭代式的,最短路径的估计值都是临时的。算法思想是不断地逼近最优解,只在最后一步才确定想要的结果。但是他们实现的方式上存在差异。正因为如此,它们的时间复杂度其实有较大差异的。在Bellman-Ford算法中,要是某个点的最短路径估计值更新了,那么我们必须对所有边指向的终点再做一次松弛操作;在SPF A算法中,某个点的最短路径估计值更新,只有以该点为起点的边指向的终点需要再做一次松弛操作。在极端情况下,后者的效率将是前者的n 倍,一般情况下,后者的效率也比前者高出不少。基于两者在思想上的相似,可以这样说,SPF A算法其实是Bellman-Ford算法的一个进一步优化的版本。

三、应用举例

我们从理论上研究问题的最终目的是更好地指导实践。

首先研究模型的建立,简单说,就是构图。

在实际中,往往不会直接告诉你,什么元素应该作为结点,什么元素应该作为边,应该如何构图。这就需要你根据题目的自身的特点,借鉴以往的解题经验,运用所学的相关知识,抽象出合适的模型,利用效率已有公论的算法高效求解,而在本文中,特指最短路算法。

3.1 例题1——货币兑换1

题意简述:

若干个货币兑换点在我们的城市中工作着。每个兑换点只能进行两种指定货币的兑换。不同兑换点兑换的货币有可能相同。每个兑换点有它自己的兑换汇率,货币A到货币B的汇率表示要多少单位的货币B才能兑换到一个单位的货币A。当然货币兑换要支付一定量的中转费。例如,如果你想将100美元兑换成俄元,汇率是29.75,中转费为0.39,那么你会兑换到(100-0.39)×29.75=2963.3975俄元。

城市中流通着N(N<=100)类货币,用数字1至N标号表示。每个货币兑换点用6个数字来描述:整数A和B是兑换货币的编号,实数RAB,CAB,RBA,CBA分别是A兑换成B和B兑换成A的汇率和中转费用。

Nick有一些第S类货币,他想在若干次交换后增加他的资金,当然这些资金最终仍是第S类货币。请你告诉他该想法能否实现。

分析:

1Ural State University Problem Archive 1162

如果我们可以求出,通过兑换每种货币可以得到的最大值,那么问题便迎刃而解了。

因为要是可以得到的第S类货币最大值都不比初值大,资金肯定无法增加;否则,得到最大值的过程就是一种解法。

从问题本身来看,求最大值也是与其特性相符的。

因为:根据兑换的公式可以看出,兑换前的货币越多,那么兑换后得到的货币也会越多。就是说,原货币越多越好。

到了这里,我们发现求最大值和我们学过的求最短路很类似,构图用最短路算法做也显得水到渠成了。

具体做法是:

将N种货币看成N个结点,将每个兑换点转化为两条有向边。根据兑换公式,目前从A货币兑换到B货币的汇率和中转费用为RAB,CAB,那么由对应的A结点向B结点连一条有向边,从A点得到的B的可能最大值为:(A目前的最大值-CAB)×RAB。

注意,这里所求的是最大值,为了转化为最短路,我们可以在数字前面加上一个负号。

更简洁的方法是利用求最短路的方法,求最长路。

由于存在负权(求最长路和负权等价),所以在这里Dijkstra算法不适用了,我们可以用Bellman-Ford算法或者SPFA算法做,这里用Bellman-Ford就够了。

需要指出一点,无论是求负权最短路还是求最长路,可能遇到的一个问题是:存在环,从而导致货币最大值不存在(因为可以沿环使最大值不断增大)。

解决的办法其实很简单,我们只需要设立一个停止条件就行了。

如果当前没有点的最优值可以更新,又或者第S个点的最优值已经优于初始值,就可以退出循环了。

在细节上还有两点要注意。一是两点间的边可能不止一条,所以存图不能用邻接矩阵(从效率的角度也不提倡用),而应该用邻接表;二是涉及比较实数的大小,判断A

至此,本题解决。

小结:

想到求最大值是个人思维能力的体现;本题能够用求最大值解,却取决于题目本身的性质;采用最短路算法求最大值,由最短路模型的适用范围决定;对于细节的处理,则要靠以往的解题经验和平时的积累。

有时候,已经知道了应该用最短路做,但是选择不同的实现方式,时空效率有较大的差别,编程复杂度也有所不同,我们应该选择在时空复杂度可以接受的情况下,编程复杂度尽可能低的方式。就是说,要找到时空复杂度和编程复杂度的平衡点,写出性价比高的程序。

3.2 例题2——双调路径2

题意简述:

2Baltic Olympiad in Informatics 2002

如今的道路密度越来越大,收费也越来越多,因此选择最佳路径是很现实的问题。城市的道路是双向的,每条道路有固定的旅行时间以及需要支付的费用。路径由连续的道路组成。总时间是各条道路旅行时间的和,总费用是各条道路所支付费用的总和。同样的出发地和目的地,如果路径A比路径B所需时间少且费用低,那么我们说路径A比路径B好。对于某条路径,如果没有其他路径比它好,那么该路径被称为最优双调路径。这样的路径可能不止一条,或者说根本不存在。

给出城市交通网的描述信息,起始点和终点城市,求最优双条路径的条数。城市不超过100个,边数不超过300,每条边上的费用和时间都不超过100。

分析:

本题显然是一道求最短路径的题目,不过和一般的问题也有所不同。

这道题棘手的地方在于标号已经不是一维,而是二维,因此不再有全序关系,初看似乎不能用最短路模型做。我们可以采用拆点法(这招在网络流问题上也很有用,比如点流量有限制的问题),让d[i,c]表示从s到i费用为c时的最短时间。

现在已经可以运用最短路算法做了。

我们面前有两条路:一是用标号设定算法,Dijkstra;二是用标号修正算法,Bellman-Ford或SPFA。

算法一:

标号设定算法是根据拓扑顺序不断把临时标号变为永久标号的。

在这题中,其实,我们并不需要严格的拓扑顺序,而只需要一个让标号永久化的理由。拓扑顺序能保证标号的永久化,但是还有其他方式。在本题中,标号永久化的条件是:从其他永久标号得不到费用不大于c且时间不大于t的临时标号(这里利用了费用和时间的非负性),即:所有的“极小临时标号”都可以永久化。这样,一个附加的好处是一次把多个临时标号同时变成永久的。

假设时间上限为t,费用上限为c,城市数为n,边数为m,则每个点上的标号不超过O(nc)个,标号总数为O(n2c)个,每条边考虑O(nc)次。如果不同顶点在同一费用的临时标号用堆来维护,不同费用的堆又组成一个堆的话,那么建立(或更新)临时标号的时间为O(mnclognlogc),总的时间复杂度为O(n2c+mnclognlogc),本题的规模是完全可以承受的。实际上由于标号的次数往往远小于n2c,程序效率是相当理想的。

算法二:

我们考虑在本题中运用SPFA算法的话,情况会是怎样?

在最坏情况下,费用最大值c为100 * 100=10000,那么每个点将被拆成10000个点,由于原图边数不超过300,所以我们构造的新图中边数不会超过3000000。

根据我们之前的讨论可以知道,SPFA算法的平均时间复杂度是O(E)的。但是最坏情况下,复杂度可以达到O(VE),对于本题而言,V=106,E=3*106,总复杂度将达到O(3*1012)之巨!

实际上,即使是用Bellman-Ford算法,O(3*1012)的情况也极少出现(要做出这种数据真的不容易),更何况是SPFA了。

所以算法的复杂度应该是O(kE),其中的k将会比V小很多。

还有一个好消息是:刚才对于时间复杂度的估计是基于一般图的,而本题非常特别。首先,费用的最大值,上限10000是很难达到的,它要求经过所有点,

并且每条边都是最大的费用100,一般来说,实际上限会比10000小很多。还有,图的构造也很特别,因为它的边是由最多只有300条边的原图拆出来的,每个结点拆出的所有点之间是相互独立的。

辅助队列应该采用循环队列,这样空间就不会浪费了。

写出来的程序运行的实际效果非常好,每个数据的速度都比官方参考程序(算法一)快,有几个甚至比官方程序快3~4倍!完全通过这题简直是轻而易举。这和我们对时间复杂度在理论上的分析是一致的。

在空间上和算法一是同阶的,一样是O(E)。虽然算法一仅用到二叉堆,并不是特别复杂,但是因为要用两个堆,建立更新删除写起来还是有一定的工作量的。SPFA算法写起来极其简单,效率又高,而且适用范围广(可以处理含有负权的图),在很多情况下,是最短路问题上好的选择。

建模和选择合适的实现方式是最短路的两个基础问题。

仅仅满足于此是远远不够的。

下面给出两道相对复杂的题目。它们的模型比较隐蔽,要求把题目抽象化,得出些本质的东西。考察的知识面也比较广泛,综合性较强。这里给出笔者思考解答的过程,力求做到:思路清晰,证明严谨,程序简洁高效。希望能抛砖引玉,对读者有所启发。

3.3 例题3——Layout3

题意简述:

当排队等候喂食时,奶牛喜欢和它们的朋友站得靠近些。FJ有N (2<=N<=1000)头奶牛,编号从1到N,沿一条直线站着等候喂食。奶牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条,所以可能有两头或者更多奶牛站在同一位置上。即使说,如果我们想象奶牛是站在一条数轴上的话,允许有两头或更多奶牛拥有相同的横坐标。

一些奶牛相互间存有好感,它们希望两者之间的距离不超过一个给定的数L。另一方面,一些奶牛相互间非常反感,它们希望两者间的距离不小于一个给定的数D。给出ML条关于两头奶牛间有好感的描述,再给出MD条关于两头奶牛间存有反感的描述。(1<=ML,MD<=10000,1<=L,D<=1000000)你的工作是:如果不存在满足要求的方案,输出-1;如果1号奶牛和N号奶牛间的距离可以任意大,输出-2;否则,计算出在满足所有要求的情况下,1号奶牛和N号奶牛间可能的最大距离。

分析:

如果当前问题比较复杂,我们应该学会“退一步”思考,由简单到复杂。

求最大值不知从何下手,我们先从容易的开始分析。

我们先研究,如果不要求输出1和N的最大距离,而只需一个可行的距离,应该如何操作。

我们用D[i]表示I号奶牛和1号奶牛间的距离。

因为在队伍中的顺序必须和编号相同,所以对于任意I号奶牛,1<=I

3Usaco Month Contest December 2005 Gold

D[I+1] - D[I] >= 0

对于每个好感的描述(i,j,k),假设i<=j,体现到距离上的要求就是:

D[j] - D[I] <= k

对于每个反感的描述(i,j,k),假设i<=j,体现到距离上的要求就是:

D[j] - D[I] >= k

这时的模型有一个名称,叫作:差分约束系统。

为了方便起见,我们将每种不等式写成我们约定的形式:

D[I] <= D[I+1]

D[j] <= D[I] + k

D[I] <= D[j] - k

看到这些不等式,你想到了什么?

没错,在求顶点间地最短路问题中,我们有这样的不等式:

若顶点u到顶点v有边e=uv,且边权为w(e),设d(u),d(v)为源点到顶点u 和顶点v的最短路长,

则d(v) <= d(u) + w(e)

这个不等式和前面的条件形式十分相似,这就启发我们用构图用最短路做。

具体步骤是:

作有向图G=(V,E),V={ v1,v2,v3,…,v n},E={e1,e2,e3,…},对于相邻两点i和(i+1),对应的顶点v i+1向v i引一条边,费用为0;对于每组好感描述(a i,b i,d i),我们假设有a i

于是问题变为在G中求v1到其它所有顶点的最短路。我们证明若G中无负权回路,则问题有解,即存在满足条件的数列,若G中有负权回路,则问题无解,即不存在满足条件的数列。

定理5 问题是否有解等价于图G是否没有负权回路。

证明:若G中无负权回路,我们可以求出v1其他顶点u的最短路长,设为d(u)。由于是最短路,因此对于任意边e E,e=uv,有d(u)+w(e)>=d(v),从而所有的约束条件都被满足,问题一定有解。若G中有负权回路,说明在任何时刻,G中至少有一个点v的最短路长可以更新,因此必须存在一条边e=uv,使得d(u)+w(e)

检测负权回路,可以用Bellman-Ford算法。

回到原问题。

先说说考试时我的做法。

将所有点的最短路估计值设为一个充分大的值,v1的最短路估计值设为0。然后运行一次Bellman-Ford。

如果图G中有负权回路,那么输出-1;

否则,如果标号为N的顶点的最短路估计仍为一个充分大的值,那么它和标号为1的顶点间的距离可以任意大,这时输出-2;

如果以上两种情况都不满足,那么输出标号为N的点的最短路径估计值。

什么是充分大呢?

只需要比原图中最大的边权×顶点数还大就行了。

因为只要无圈,每个顶点最多只会被经过一次,所以肯定比这个值小,所以在该图中,我们可以把这个值看作是无穷大。

该方法可以通过竞赛的所有测试数据。

考试的时候,我没有去刻意证明这个方法的正确性,只是感觉它应该可行。

现在让我们从理论上证明它。

定理6 若运行Bellman-Ford后,标号为N的顶点的最短路估计值仍为充分大,那么N和1的距离可以任意大。

证明:从刚才的操作可以看出,到了这一步,已经把含有负权回路的情况排除掉了。在图G中,该充分大的值比可能得到的最大距离大,因此,它和任意大的值对于G的效果都是一样的(同样大于合法的最大距离)。由于充分大的值在G中满足约束,所以任意大的值亦满足约束,从而距离可以任意大。(证毕)剩下还有一个问题。

定理7 若运行Bellman-Ford后,标号为N的顶点的最短路估计值比充分大小,那么它是N和1可能的最大距离。

证明:设D[i]是顶点i和1的最短路径估计值,d[i]是顶点i和1可能的最大距离。

我们首先证明,d[n]<=D[n],运用反证法。

假如d[n]>D[n],那么在Bellman-Ford运行之前,将赋予每个顶点i的充分大的值换成对应的d[i]。由于d本身满足所有约束条件,所以运行后,得出D'=d。由于充分大的值比所有d[i]都大,而求最短路运用的是逐步松弛操作,我们设立一个更大的初值不可能导致我们的终值反而更小。所以对于任意i,必定有D[i]>=D'[i],即有D[n]>=d[n],这与我们的假设矛盾。

然后我们证明,d[n]>=D[n]。

根据d[i]的定义,它是i和1的可能最大距离。由于D[i]是满足题目的所有约束的,所以D[i]是顶点i和1可能的距离。如果D[i]>d[i],那么与d[i]的定义矛盾。

综合上述,有D[i]=d[i]。从而D[n]是n和1可能的最大距离。(证毕)

运行Bellman-Ford最坏情况下的复杂度是O((ML+MD)*N)=O(2*107),可以在规定时间内出解。另外,实际运行的速度相当理想,大部分数据运行基本上不需要时间。

3.4 例题4——网络提速4

某学校的校园网由n(1<=n<=50)台计算机组成,计算机之间由网线相连,如图5。其中顶点代表计算机,边代表网线。正如你所见,不同网线的传输能力不尽相同,例如计算机1与计算机2之间传输信息需要34秒,而计算机2与计算机3之间的传输信息只要10秒。计算机1与计算机5之间传输信息需要44秒,途径为机1到机3到机5。

现学校购买了m(1<=m<=10)台加速设备,每台设备可作用于一条网线,使网线上传输信息用时减半。多台设备可用于同一条网线,其效果叠加,即用两台设备,用时为原来的1/4,用三台设备,用时为原来的1/8。如何合理使用这些设备,使计算机1到计算机n传输用时最少,这个问题急需解决。校方请你编程

4经典问题

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

图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 台设备用在那条边上,行不行呢?

经过简单的举例后发现行不通。

一个明显的反例是: 30

20

16 24 10

12 34 4 2

5 3

1

图6

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

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

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

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

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

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

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

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

为什么?

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

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

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

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

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

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

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

V={v i,0,v i,1,v i,2,……,v i,m|v i∈V0}

对于原图的每一条边,注意是无向的,e k=v i v j∈E

0,将它拆成(m+1)(m+2)

40 8

16 1 2

4 3

1

条有向边(e k )0,0=v i,0v j,0,(e k )0,1=v i,0v j,1,……,(e k )m,m =v i,m v j,m ,(e k )'0,0=v j,0v i,0,(e k )'0,1=v j,0v i,1,……(e k )'m,m =v j,m v i,m 。构造E 使得

E={(e k )p,q =v i,p v j,q ,(e k )'p,q =v j,p u i,q |e k =v i v j ∈E 0,0<=p<=q<=m}

最后设定权函数w 。对于v i,p v j,q ∈E ,w 满足:

w(v i,p v j,q )=w(v i v j )×2q-p

解释一下图G 的含义。

为了更清楚地说明问题,我们举出一个例子。图7(a)显示了某个

G 0(n=2,m=2),按照以上的构造方法得出图7(b)中的G 。将图G 分成三层,第0层由顶点v 1,0,v 2,0构成,第1层由顶点v 1,1,v 2,1构成,第2层由顶点v 1,2,v 2,2构成。可以看出,若两个顶点间有边相连,两个顶点在同一层的,则顶点之间是互连的,若不在同一层,则层号小的顶点为边的起始点,层号大的为边的终点。

图7

层号代表已用的加速设备台数,例如从v 1,0到v 2,1需要且恰好要用一台加

速设备。我们无法从层号大的顶点到达层号小的顶点,这符合同一个设备不能使用多次的规定。

剩下的工作就是对图G 使用Dijkstra 算法求v 1,0到v n,m 的最短路长。相信

大家都会,我就不多说了。

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

四、总结

本文首先介绍了最短路的一些相关概念,它们是后边介绍的三种算法的基

础。其中的某些性质对于建立最短路模型十分有用。

Dijkstra 算法的效率高,但是也有局限性,就是对于含负权的图无能为力。

Bellman-Ford 算法对于所有最短路长存在的图都适用,但是效率常常不尽

人意。

SPFA 算法可以说是综合了上述两者的优点。它的效率同样很不错,而且

对于最短路长存在的图都适用,无论是否存在负权。它的编程复杂度也很低,是性价比极高的算法。

在不含负权的图中,特别是在边数稠密的图中,我们常常选择Dijkstra 算8 (a) 8 8 4 4 2

2 4

4 8

1 2 1,0

1,2

2,2 2,1 1,1

2,0 (b)

法,在稀疏图中,二叉堆实现的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.

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

最短路算法[1]

最短路算法及其应用 广东北江中学余远铭【摘要】 最短路问题是图论中的核心问题之一,它是许多更深层算法的基础。同时,该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系,却也可以归结为最短路问题。本文较详尽地介绍了相关的基本概念、常用算法及其适用范围,并对其应用做出了举例说明,侧重于模型的建立、思考和证明的过程,最后作出总结。 【关键字】 最短路 【目录】 一、基本概念 (2) 1.1 定义 (2) 1.2简单变体 (2) 1.3负权边 (3) 1.4重要性质及松弛技术 (4) 二、常用算法 (5) 2.1 Dijkstra算法 (5) 2.2 Bellman-Ford算法 (7) 2.3 SPFA算法 (8) 三、应用举例 (10) 3.1 例题1——货币兑换 (10) 3.2 例题2——双调路径 (11) 3.3 例题3——Layout (13) 3.4 例题4——网络提速 (15) 四、总结 (18)

【正文】 一、基本概念 1.1 定义 乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并 在地图上标出了每对十字路口之间的距离,如何找出这一最短行程? 一种可能的方法是枚举出所有路径,并计算出每条路径的长度,然后选择最短的一条。然而我们很容易看到,即使不考虑含回路的路径,依然存在数以百万计的行车路线,而其中绝大多数是没必要考虑的。 下面我们将阐明如何有效地解决这类问题。在最短路问题中,给出的是一 有向加权图G=(V ,E),在其上定义的加权函数W:E →R 为从边到实型权值的映射。路径P=(v 0, v 1,……, v k )的权是指其组成边的所有权值之和: 11()(,)k i i i w p w v v -==∑ 定义u 到v 间最短路径的权为 {}{}min ():)w p u v u v v δυ→(,=∞ 如果存在由到的通路 如果不存在 从结点u 到结点v 的最短路径定义为权())w p v δυ=(,的任何路径。 在乘车旅行的例子中,我们可以把公路地图模型化为一个图:结点表示路口,边表示连接两个路口的公路,边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。 边的权常被解释为一种度量方法,而不仅仅是距离。它们常常被用来表示 时间、金钱、罚款、损失或任何其他沿路径线性积累的数量形式。 1.2简单变体 单目标最短路径问题: 找出从每一结点v 到某指定结点u 的一条最短路 径。把图中的每条边反向,我们就可以把这一问题转化为单源最短路径问题。 单对结点间的最短路径问题:对于某给定结点u 和v ,找出从u 到v 的一 条最短路径。如果我们解决了源结点为u 的单源问题,则这一问题也就获得了解决。对于该问题的最坏情况,从渐进意义上看,目前还未发现比最好的单源算法更快的方法。 每对结点间的最短路径问题:对于每对结点u 和v ,找出从u 到v 的最短 路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。

蚁群算法在最短路中的应用

下面的程序是蚁群算法在最短路中的应用,稍加扩展即可应用于机器人路径规划function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.sodocs.net/doc/4610990614.html, % All rights reserved %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵,如果为1表示障碍物 % Tau 初始信息素矩阵(认为前面的觅食活动中有残留的信息素) % K 迭代次数(指蚂蚁出动多少波) % M 蚂蚁个数(每一波蚂蚁有多少个) % S 起始点(最短路径的起始点) % E 终止点(最短路径的目的点) % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模(象素个数)

短路电流计算公式

变压器短路容量-短路电流计算公式-短路冲击电流的计算发布者:admin 发布时间:2009-3-23 阅读:513次供电网络中发生短路时,很大的短路电流会使电器设备过热或受电动力作用而遭到损坏,同时使网络内的电压大大降低,因而破坏了网络内用电设备的正常工作。为了消除或减轻短路的后果,就需要计算短路电流,以正确地选择电器设备、设计继电保护和选用限制短路电流的元件。 二.计算条件 1.假设系统有无限大的容量.用户处短路后,系统母线电压能维持不变.即计算阻抗比系统阻抗要大得多。 具体规定: 对于3~35KV级电网中短路电流的计算,可以认为110KV及以上的系统的容量为无限。只要计算35KV及以下网络元件的阻抗。 2.在计算高压电器中的短路电流时,只需考虑发电机、变压器、电抗器的电抗,而忽略其电阻;对于架空线和电缆,只有当其电阻大于电抗1/3时才需计入电阻,一般也只计电抗而忽略电阻。 3. 短路电流计算公式或计算图表,都以三相短路为计算条件。因为单相短路或二相短路时的短路电流都小于三相短路电流。能够分断三相短路电流的电器,一定能够分断单相短路电流或二相短路电流。 三.简化计算法 即使设定了一些假设条件,要正确计算短路电流还是十分困难,对于一般用户也没有必要。一些设计手册提供了简化计算的图表.省去了计算的麻烦.用起来比较方便.但要是手边一时没有设计手册怎么办?下面介绍一种“口诀式”的计算方法,只要记牢7句口诀,就可掌握短路电流计算方法。 在介绍简化计算法之前必须先了解一些基本概念。 1.主要参数 Sd三相短路容量(MV A)简称短路容量校核开关分断容量 Id三相短路电流周期分量有效值(KA)简称短路电流校核开关分断电流和热稳定 IC三相短路第一周期全电流有效值(KA) 简称冲击电流有效值校核动稳定 ic三相短路第一周期全电流峰值(KA) 简称冲击电流峰值校核动稳定 x电抗(W) 其中系统短路容量Sd和计算点电抗x 是关键. 2.标么值 计算时选定一个基准容量(Sjz)和基准电压(Ujz).将短路计算中各个参数都转化为和该参数的基准量的比值(相对于基准量的比值),称为标么值(这是短路电流计算最特别的地方,目的是要简化计算). (1)基准 基准容量Sjz =100 MV A 基准电压UJZ规定为8级. 230, 115, 37, 10.5, 6.3, 3.15 ,0.4, 0.23 KV 有了以上两项,各级电压的基准电流即可计算出,例: UJZ (KV)3710.56.30.4

短路电流计算方法

供电网络中发生短路时,很大的短路电流会使电器设备过热或受电动力作用而遭到损坏,同时使网络内的电压大大降低,因而破坏了网络内用电设备的正常工作.为了消除或减轻短路的后果,就需要计算短路电流,以正确地选择电器设备、设计继电保护和选用限制短路电流的元件。 二.计算条件 1.假设系统有无限大的容量.用户处短路后,系统母线电压能维持不变.即计算阻抗比系统阻抗要大得多。 具体规定: 对于3~35KV级电网中短路电流的计算,可以认为110KV及以上的系统的容量为无限大.只要计算35KV及以下网络元件的阻抗。 2.在计算高压电器中的短路电流时,只需考虑发电机、变压器、电抗器的电抗,而忽略其电阻;对于架空线和电缆,只有当其电阻大于电抗1/3时才需计入电阻,一般也只计电抗而忽略电阻。 3. 短路电流计算公式或计算图表,都以三相短路为计算条件.因为单相短路或二相短路时的短路电流都小于三相短路电流.能够分断三相短路电流的电器,一定能够分断单相短路电流或二相短路电流。 三.简化计算法 即使设定了一些假设条件,要正确计算短路电流还是十分困难,对于一般用户也没有必要.一些设计手册提供了简化计算的图表.省去了计算的麻烦.用起来比较方便.但要是手边一时没有设计手册怎么办?下面介绍一种“口诀式”的计算方法,只要记牢7句口诀,就可掌握短路电流计算方法. 在介绍简化计算法之前必须先了解一些基本概念. 1.主要参数 Sd三相短路容量 (MVA)简称短路容量校核开关分断容量 Id三相短路电流周期分量有效值(KA)简称短路电流校核开关分断电流 和热稳定 IC三相短路第一周期全电流有效值(KA) 简称冲击电流有效值校核动稳定 ic三相短路第一周期全电流峰值(KA) 简称冲击电流峰值校核动稳定 x电抗(Ω) 其中系统短路容量Sd和计算点电抗x 是关键. 2.标么值

图论及其应用(精)

图论及其应用 学时:40 学分:2 课程属性:专业选修课开课单位:理学院 先修课程:高等代数后续课程:无 一、课程的性质 《图论及其应用》是数学与应用数学专业的专业选修课程。 二、教学目的 通过教学,使学生掌握图论及其算法的基本理论和基本技巧,初步掌握图论及其算法的基本应用手段、基本算法设计及编程,并能用所学理论解决一些应用问题。 三、教学内容 1.图的基本概念 2.图的连通性 3.树的基本性质及其应用 4.Euler Graphs and Hamilton Graphs with Applications 5.平面图性质 6.匹配,求最大匹配算法及应用 7.图的染色及应用 8.极图理论 四、学时分配 章课程内容学时 1 图的基本概念 4 2 图的连通性 6 3 树的基本性质及其应用 6 4 Euler Graphs and Hamilton Graphs with Applications 4 5 平面图性质 6 6 匹配,求最大匹配算法及应用 6

7 图的染色及应用 4 8 极图理论 4 合计40 五、教学方式 本课程采用多媒体课堂讲授,结合实际范例深入浅出讲解讨论。 六、考核方式 本课程考核采用平时与期末考核相结合的办法,特别注重平时的考核,作业采用简单练习、论文等形式,期末考试采用简单考题或论文形式。 七、教材及教学参考书 参考教材: [1] J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macmillan Press LTD,1976. [2] 蒋长浩.图论与网络流.北京:中国林业出版社,2000. 参考书目: [1] Bela Bollobas.Modern Graph Theory(现代图论,影印版).北京:科学出版社,2001. [2] 殷剑宏、吴开亚.图论及其算法.合肥:中国科学技术大学出版社,2003. [3] 谢金星、邢文训.网络优化.北京:清华大学出版社.2000. [4] 程理民、吴江、张玉林.运筹学模型与方法教程.北京:清华大学出版社,2000. [5] 三味工作室.SPSS V10.0 for Windows 实用基础教程.北京:北京希望电子出版社2001. [6] 孙魁明、张海彤.Mathematica工具软件大全.北京:中国铁道出版社,1994. [7] 楼顺天、于卫、闫华梁.MATLAB程序设计语言.西安:西安电子科技大学出版社,1997.八、教学基本内容及要求 第一章图的基本概念 1.教学基本要求 掌握的图的基本概念、特殊图概念,了解最短路问题。 2.教学具体内容 图的基本概念,路和圈,最短路问题。

(完整版)短路电流的计算方法

第七章短路电流计算 Short Circuit Current Calculation §7-1 概述General Description 一、短路的原因、类型及后果 The cause, type and sequence of short circuit 1、短路:是指一切不正常的相与相之间或相与地(对于中性点接地 的系统)发生通路的情况。 2、短路的原因: ⑴元件损坏 如绝缘材料的自然老化,设计、安装及维护不良等所造成的设备缺陷发展成短路. ⑵气象条件恶化 如雷击造成的闪络放电或避雷器动作;大风造成架空线断线或导线覆冰引起电杆倒塌等. ⑶违规操作 如运行人员带负荷拉刀闸;线路或设备检修后未拆除接地线就加电压. ⑷其他原因 如挖沟损伤电缆,鸟兽跨接在裸露的载流部分等. 3、三相系统中短路的类型: ⑴基本形式: )3(k—三相短路;)2(k—两相短路; )1( k—单相接地短路;)1,1(k—两相接地短路; ⑵对称短路:短路后,各相电流、电压仍对称,如三相短路; 不对称短路:短路后,各相电流、电压不对称; 如两相短路、单相短路和两相接地短路. 注:单相短路占绝大多数;三相短路的机会较少,但后果较严重。4、短路的危害后果 随着短路类型、发生地点和持续时间的不同,短路的后果可能只破坏局部地区的正常供电,也可能威胁整个系统的安全运行。短路的危险后果一般有以下几个方面。 (1)电动力效应 短路点附近支路中出现比正常值大许多倍的电流,在导 体间产生很大的机械应力,可能使导体和它们的支架遭 到破坏。 (2)发热 短路电流使设备发热增加,短路持续时间较长时,设备 可能过热以致损坏。 (3)故障点往往有电弧产生,可能烧坏故障元件,也可能殃

短路电流 计算方法 口诀

短路电流计算方法口诀 一.概述 供电网络中发生短路时,很大的短路电流会使电器设备过热或受电动力作用而遭到损坏,同时使网络内的电压大大降低,因而破坏了网络内用电设备的正常工作.为了消除或减轻短路的后果,就需要计算短路电流,以正确地选择电器设备、设计继电保护和选用限制短路电流的元件. 二.计算条件 1.假设系统有无限大的容量.用户处短路后,系统母线电压能维持不变.即计算阻抗比系统阻抗要大得多. 具体规定: 对于3~35KV级电网中短路电流的计算,可以认为110KV及以上的系统的容量为无限大.只要计算35KV及以下网络元件的阻抗. 2.在计算高压电器中的短路电流时,只需考虑发电机、变压器、电抗器的电抗,而忽略其电阻;对于架空线和电缆,只有当其电阻大于电抗1/3时才需计入电阻,一般也只计电抗而忽略电阻. 3. 短路电流计算公式或计算图表,都以三相短路为计算条件.因为单相短路或二相短路时的短路电流都小于三相短路电流.能够分断三相短路电流的电器,一定能够分断单相短路电流或二相短路电流. 三.简化计算法

即使设定了一些假设条件,要正确计算短路电流还是十分困难,对于一般用户也没有必要.一些设计手册提供了简化计算的图表.省去了计算的麻烦.用起来比较方便.但要是手边一时没有设计手册怎么办?下面介绍一种“口诀式”的计算方法,只要记牢7句口诀,就可掌握短路电流计算方法. 在介绍简化计算法之前必须先了解一些基本概念. 1.主要参数 Sd三相短路容量(MVA)简称短路容量校核开关分断容量 Id三相短路电流周期分量有效值(KA)简称短路电流校核开关分断电流 和热稳定 IC三相短路第一周期全电流有效值(KA) 简称冲击电流有效值校核动稳定 ic三相短路第一周期全电流峰值(KA) 简称冲击电流峰值校核动稳定 x电抗(Ω) 其中系统短路容量Sd和计算点电抗x 是关键. 2.标么值 计算时选定一个基准容量(Sjz)和基准电压(U jz).将短路计算中各个参数都转化为和该参数的基准量的比值(相对于基准量的比值),称为标么值(这是短路电流计算最特别的地方,目的是要简化计算).

最短路问题及其应用——最短路径

最短路问题及应用 摘要:主要介绍最短路的两种算法,迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法以及这两种算法在实际问题中的应用和比较。 关键词:最短路获克斯特拉(Dijkstra),弗罗伊德(Floyd)算法 1.引言 图论是应用数学的一个分支,它的概念和结果来源非常广泛,最早起源于一些数 学游戏的难题研究,如欧拉所解决的哥尼斯堡七桥问题,以及在民间广泛流传的一些游戏难题,如迷宫问题、博弈问题、棋盘上马的行走路线问题等。这些古老的难题,当时吸引了很多学者的注意。在这些问题研究的基础上又继续提出了著名的四色猜想 和汉米尔顿(环游世界)数学难题。 1847年,图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学的发展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学 等各个领域的问题时,发挥出越来越大的作用在实践中,图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点 间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学 与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2.最短路算法 2.1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图()0 w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该ij 算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短

变压器短路电流的实用计算方法

变压器短路电流的实用计算方法 胡浩,杨斌文,李晓峰 (湖南文理学院,湖南常德415000) 基金项目:湖南省科技厅计划项目(2007FJ3046) 1前言 在电力系统中,对于电气设备的选用、电气接线方案的选择、继电保护装置的设计与整定以及有关设备热稳定与动稳定的校验等工作,都需要对变压器的短路电流进行计算。短路电流的计算,一般采用有名制或标幺值算法,再者是应用曲线法。然而,无论哪种方法应用起来都比较繁琐,尤其是对于企业的技术人员与农村的电工,因缺乏相应的技术资料,又不能从变压器铭牌上查到所有计算短路电流的数据,所以想快速算出短路电流值是相当困难的。笔者在多年的实际工作中,依据变压器的基本原理与基本关系式,总结出快速计算短路电流值的实用方法,以满足现场与工程上的需要。 2变压器低压三相短路时高压侧短路电流的计算 变压器的阻抗电压是在额定频率下,变压器低压绕组短接,高压绕组施加逐步增大的电压,当高压绕组中的电流达到额定电流时,所施加的电压为阻抗电压Ud,一般以高压侧额定电压U1N为基础来表示: Ud%=Ud/U1N×100% (1) 由变压器的等值电路可知,低压侧短路后的阻抗折算到高压侧,与高压侧阻抗相加后得总的阻抗Zd,在阻抗电压Ud时,高压绕组电流为额定值I1N, 即: I1N=Ud/Zd (2) 如果高压绕组的电压为U1,则此时高压绕组的电流I1为: I1=U1/Zd (3) 由式(2)和式(3)可得: I1=U1/Ud*I1N (4) 对于单个变压器,其容量远小于电力系统的容量,故可以认为当变压器低压侧出现短路时,高压侧电压不变,即为U1N,代入式(4)就可得到变压器低压侧短路时,高压侧的短路电流I1d: I1d=U1N/Ud*I1N (5) 将式(1)中的Ud代入式(5)得: I1d=I1N/Ud%×100 (6) 而变压器高压绕组的额定电流I1N可表示为: I1N=SN/√3U1N (7) 式中SN———变压器的额定容量 将式(7)代入式(6)可得: I1d=100SN/√3U1NUd% (8) 由式(6)或式(8)可计算出变压器低压三相短路时,高压侧的短路电流值。 3变压器低压三相短路时低压侧短路电流的计算 由于变压器的励磁电流仅为I1N的1%~3%,忽略励磁电流,则高、低压绕组的电流I1、I2与电压U1、 U2的关系为: I1/I2=U2/U1=U2N/U1N 式中

关于最短路问题算法的一点思考

关于最短路问题算法的一点思考 最短路问题,实际上是P95。也就是我们用一个算法解决SP问题时,就是在找这个加权图G中从s到t的P(s,t)中边权之和最小的P*(s,t). 由定义就可以看出,实际生活中经常有最短路问题的例子。例如: 实例1.某公司在六个城市s,t,a,b都有分公司,公司成员经常往来于它们之间,已知从Vi到Vj的直达航班票价由下述矩阵的第i行,第j列元素给出(∞表示无直达航班),该公司想算出一张任意两个城市之间的最廉价路线航费表。 图+矩阵 实例2.如图的交通网络,每条弧上的数字代表车辆在该路段行驶所需的时间,有向边表示单行道。若有一批货物要从s号顶点运往t号顶点,问运货车应沿哪条线路行驶,才能最快地到达目的地? 图+矩阵 因此怎么样快速又精确的求解一个最短路问题就显得至关重要。下面我们来介绍几种解决SP问题的有效途径。 一、把求最短路问题转化为LP问题 P95 二、最短路问题的原始对偶算法:Dijkstra算法 Pdf最短路+课本P138 综上,即为Dijkstra算法,它的有效实施体现在:P161 对Dijkstra算法的一点思考: 1.关于Dijkstra算法,书中的例子定义了一个使用范围,即寻求有向图中,从一固定顶点到其余各点的最短路径。那么一个简单的推广就是在于,对于无向图或者混合图的情况Dijkstra算法还能否使用?答案应该是肯定的。也就是说,实例2中无论是单行道,双行道的情况都是可以应用Dijkstra算法进行求解的。 2. 作为学习图论的一名学生,Dijkstra算法的本质可以说就是在一个图中,进行标号,每次迭代产生一个永久标号, 从而生长一颗以s为根的最短路树,在这颗树上每个顶点与根s 节点之间的路径皆为最短路径. 3.Dijkstra算法明确要求权(费用)非负,这无疑会限制一些是实际生活中的例子进行求解,若出现的边权为负的情况,Dijkstra算法就要进行修改。并且,如果我们对Dijkstra算法进行编程,即使根据书中拟Algol语言的提示以我现有的水平也根本写不出Matlab的高级程序语言。但是有另外一种算法有效的避免了这个麻烦,它的逻辑更为简单,并允许网络中的弧有负权,能探测网络中负费用圈,与一般的原始对偶算法不同。 三、Floyd-Warshall算法 P164 并且,有一点比较吸引我的地方是在于Floyd-Warshall算法的逻辑较为简单,我可以跟据课本上拟Algol语言,编写出一部分Matlab的程序,但是因为编译程序的水平的限制,每次运行的时候都会出现不同的错误。在与计算数学的同学进行讨论的时候,因为他们偏重绘图而我们偏重优化,导致也为得出有效的解决措施。

短路计算公式

短路计算 1、在下图所示网络中,设G 为无穷大系统,A MV S B ?=100,B av U U =,sh 1.8K =,求K 点发生三相短路时的冲击电流、短路电流的最大有效值、短路功率。 (*B G NT S X S =,*%100k B T NT U S X S =?,*02B L L S X X L U = ,*R R X X =) 40km U k %=10.5 6.3kV X R %=4 0.5km 解:解:采用标幺值的近似计算法: 各元件电抗的标幺值: G 为无穷大系统,故系统阻抗为零, 1*2 **2*2100 400.40.12111510.51000.35 10030 44 1.222 100100100 0.50.080.1008 6.3L T B R N L X X I X I X =?? ==?==?===??= 则从短路点看进去的总电抗的标幺值: 7937.1*2***1*=+++=∑L R T L k X X X X X 短路点短路电流的标幺值,近似认为短路点的开路电压k U 为该段的平均额定电压av U 5575.01 * ***=== ∑∑X X U I k k 短路点短路电流的有名值 kA I I I B k k 113.53 .63100 5575.0*=?? =?= 冲击电流kA I i k sh 01.13113.555.255.2=?== 最大有效值电流kA I I k sh 766.7113.552.152.1=?== 短路功率:A MV I I S S S B k B k k ?=?=?=?=75.551005575.0**

两种计算短路电流的方法

某企业供电系统,A 是电源母线,通过两条架空线路1l 向设有两台主变压器T 的终端变电所35kV 母线B 供电。6kV 侧母线C 通过串有电抗器L 的两条电缆线路2l 向一分厂变电所D 供电。整个系统并联运行。试求k1、k2、k3点的短路电流。 已知MVA s k 560=,km l 201=,km x /4.001Ω=,kV kVA T 35/56002:?,5.7%=k U ; L:kV U LN 6=,A I LN 200=,3%=L X ;km l 5.02=,km x /08.002Ω= (一)常规算法 解:1.各元件电抗 电源的电抗 Ω=== 44.2560 3722k av S S U X 架空线1l 的电抗 Ω8204.01011=?==l x X l 架空线2l 的电抗 Ω04.05.008.02022=?==l x X l 变压器的电抗 Ω33.186 .5371005.7100%2 .2=?=?=N T av T S U U X 电抗器的电抗 Ω52.0200 36000 %33% =??==LN LN L L I U X X 电缆内阻可以忽略不计。 2.计算各点的短路总阻抗 k1点短路时,电路总阻抗为 44.62 8 44.22 11=+ =+ =l k k X X X

k2点短路时,电路总阻抗为 Ω452 .0)373.6(23.1844.6)373.6)(2(22 2212 =???? ? ?+=+=T k k X X X k3点短路时,电路总阻抗为 Ω732.026.002.0452.02 22 23=++=++ =l LN k k X X X X 3.各点的短路电流 k1点 kA X U I k av k 32.344 .6337 31)3(1=?== kA I i k sh 46.832.355.255.2) 3(11=?== kA I I k sh 05.532.352.152.1)3(11=?== MVA I U S k av k 213 32.33733)3(11=??== k2点 kA X U I k av k 05.8452 .033 .632) 3(2=?== A I i k sh k 5.2005.855.255.2) 3(22=?== A I I k sh k 2.1205.852.152.1)3(22=?== MVA I U S k av k 8.8705.83.633)3(22=??== k3点 kA X U I k av k 97.4732 .033 .633) 3(3=?== A I i k sh k 7.1297.455.255.2) 3(33=?== A I I k sh k 55.797.452.152.1)3(33=?== MVA I U S k av k 2.5497.43.633)3(33=??== (二)采用标么值计算 基准值的选择,取kV U kV U MVA S d d d 3.6,37,5021=== 则 kA I kA I d d 59.4,78.021==

短路电流计算计算方法.docx

短路电流计算 > 计算方法 短路电流计算 > 计算方法短路电流计算方法一、高压短 路电流计算(标幺值法) 1、基准值 选择功率、电压、电流电抗的基准值分别为、、、时,其对应关系为: 为了便于计算通常选为线路各级平均电压;基准容量 通常选为 100MVA 。由基准值确定的标幺值分别如下: 式中各量右上标的“ * “用来表示标幺值右,下标的“ d”表示在基准值下的标幺值。 2、元件的标幺值计算 (1)电源系统电抗标幺值 —电源母线的短路容量 (2)变压器的电抗标幺值 由于变压器绕组电阻比电抗小得多,高压短路计算时 忽略变压器的绕组电阻,以变压器的阻抗电压百分数(% )

作为变压器的额定电抗,故变压器的电抗标幺值为: —变压器的额定容量,MVA (3)限流电抗器的电抗标幺值 % —电抗器的额定百分电抗—电抗器额定电压, kV —电抗器的额定电流, A (4)输电线路的电抗标幺值 已知线路电抗,当=时 —输电线路单位长度电抗值,Ω/km 3、短路电流计算 计算短路电流周期分量标幺值为 —计算回路的总标幺电抗值 —电源电压标幺值,在=时, =1 = 短路电流周期分量实际值为 = 对于电阻较小,电抗较大(<1/3 )的高压供电系统,三相短路电流冲击值=2.55三相短路电流最大有效值

=1.52 常用基准值 (=100MVA) 电网额定电压(kV ) 3.0 6.0 10.0 35.0 60.0 110 基准电压( kV ) 3.15 6.3 10.5 37 63 115 基准电流( kA ) 18.3 9.16

5.5 1.56 0.92 0.502 二、低压短路电流计算(有名值法) 1. 三相短路电流 2.两相短路电流 3.三相短路电流和两相短路电流之间的换算关系 4.总电阻和总电抗 5.系统电抗 6.高压电缆的阻抗 7.变压器的阻抗

最短路算法

我写的Dijkstra最短路算法通用Matlab程序%dijkstra最短路算法通用程序,用于求从起始点s到其它各点的最短路 %D为赋权邻接矩阵,d为s到其它各点最短路径的长度,DD记载了最短路径生成树function [d,DD]=dijkstra_aiwa(D,s) [m,n]=size(D); d=inf.*ones(1,m); d(1,s)=0; dd=zeros(1,m); dd(1,s)=1; y=s; DD=zeros(m,m); DD(y,y)=1; counter=1; while length(find(dd==1))

for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)

短路电流计算的方法

短路电流计算的方法 一、 网络的等值变换与化简 为计算不同短路点的短路电流值,需将等值网络分别化简为以短路点为衷心的辐射性等值网络,并求出个电源与短路点之间的转移电抗md X 。 1、 网络等值变换 在工程计算中,常用等值变换法进行化简,其原则是网络变换前后,应使未变换部分的电话和电流分布保持不变,常用的如星三角变换(查相关手册)。 2、 并联电源支路的合并(图) 112212121n n z n n n E y E y E y E y y y X y y y +++?=?+++???=?+++? 二、 三相短路电流周期分量的计算 1、 求计算电抗js X 计算电抗js X 是将各电源与短路点之间的转移阻抗md X 归算到以各供电电源(等值发电机)容量为基准值的电抗标幺值。 ..e m js m md j S X X S = 2、 无限大容量电源的短路电流计算 由无限大容量电源供给的短路电流,或者计算电抗3js X ≥时的短路电流,可以认为周期分量不衰减。短路电流标幺值: ** ''*1z X I X ∑= 或 *1z js X X = 其有名值:*''0.2z z j I I I I I I ∞====(kA ) ;j S I =式中:

*X ∑:无穷大容量电源到短路点之间的总阻抗(标幺值) ; ''I :0秒的短路电流(kA ) ; I ∞:稳态的短路电流(kA ) ; 3、 有限容量电源的电路电流计算 通常采用使用运算曲线法,查表,注意折算电抗。 4、 短路点短路电流周期分量 将2、3中所求得的所有短路电流相加。 三、 三相短路电流非周期分量的计算 1、 单支路的短路电流费周期分量计算 按下述公式计算: 起始值:''0fz i = t 秒值:''0a a t T T fzt fz i i e e ω--== 其中:a X T R ∑ ∑= (衰减时间常数) 2、 多支路的短路电流非周期分量计算 复杂网络中个独立支路的衰减时间常数相差较大时,可采用多支路叠加法。衰减时间常数相近的分支可以归并简化,复杂的常仅近似化简为3~4个独立分支的等值网络,多数情况下化简为两个等值网络:系统支路(15a T ≤)和发电机支路(1580a T ≤≤)。对n 支路的系统: 起始值:''''''012)fz n i I I I =+++ t 秒值:12''''''12)a a an t t t T T T fzt n i I e I e I e ωωω---=+++ 3、 等效衰减时间常数 查表 四、 冲击电流和全电流计算 1、冲击电流 三相短路发生后的半个周期(0.01s ),短路电流瞬时值达到最大,称

最短路算法程序

Floyd最短路径算法 在图论中经常会遇到这样的问题,在一个有向图里,求出任意两个节点之间的最短距离。我们在离散数学、数据结构课上都遇到过这个问题,在计算机网络里介绍网络层的时候好像也遇到过这个问题,记不请了... 但是书本上一律采取的是Dijkstra算法,通过Dijkstra算法可以求出单源最短路径,然后逐个节点利用Dijkstra算法就可以了。不过在这里想换换口味,采取Robert Floyd提出的算法来解决这个问题。下面让我们先把问题稍微的形式化一下: 如果有一个矩阵D=[d(ij)],其中d(ij)>0表示i城市到j城市的距离。若i与j之间无路可通,那么d(ij)就是无穷大。又有d(ii)=0。编写一个程序,通过这个距离矩阵D,把任意两个城市之间的最短与其行径的路径找出来。 我们可以将问题分解,先找出最短的距离,然后在考虑如何找出对应的行进路线。如何找出最短路径呢,这里还是用到动态规划的知识,对于任何一个城市而言,i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能,所以可以令k=1,2,3,...,n(n 是城市的数目),在检查d(ij)与d(ik)+d(kj)的值;在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离,因此d(ik)+d(kj)就是i到j经过k的最短距离。所以,若有d(ij)>d(ik)+d(kj),就表示从i出发经过k再到j的距离要比原来的i到j距离短,自然把i 到j的d(ij)重写为d(ik)+d(kj),每当一个k查完了,d(ij)就是目前的i到j的最短距离。重复这一过程,最后当查完所有的k时,d(ij)里面存放的就是i到j之间的最短距离了。所以我们就可以用三个for循环把问题搞定了,但是有一个问题需要注意,那就是for循环的嵌套的顺序:我们可能随手就会写出这样的程序,但是仔细考虑的话,会发现是有问题的。 for(int i=0; i...->p->j,也就是说p是i到j的最短行径中的j之前的最后一个城市。P矩阵的初值为p(ij)=i。有了这个矩阵之后,要找最短路径就轻而易举了。对于i到j而言找出p(ij),令为p,就知道了路径i->...->p->j;再去找p(ip),如果值为q,i到p的最短路径为i->...->q->p;再去找p(iq),如果值为r,i 到q的最短路径为i->...->r->q;所以一再反复,到了某个p(it)的值为i时,就表示i到t 的最短路径为i->t,就会的到答案了,i到j的最短行径为i->t->...->q->p->j。因为上述的算法是从终点到起点的顺序找出来的,所以输出的时候要把它倒过来。 但是,如何动态的回填P矩阵的值呢?回想一下,当d(ij)>d(ik)+d(kj)时,就要让i到j 的最短路径改为走i->...->k->...->j这一条路,但是d(kj)的值是已知的,换句话说,就是 k->...->j这条路是已知的,所以k->...->j这条路上j的上一个城市(即p(kj))也是已知的,

短路电流计算方法及习题

三相短路的有关物理量 1)短路电流周期分量有效值: 短路点的短路计算电压(或称平均额定电压),由于线路首端短路时 其短路最为严重,因此按线路首端电压考虑,即短路计算电压取为比 线路额定电压高5%,按我国标准有,, ,,,37,69,…… 短路电流非周期分量最大值: 2)次暂态短路电流: 短路电流周期分量在短路后第一个周期的有效值。 3)短路全电流有效值: 指以时间t 为中心的一个周期内,短路全电流瞬时值的均方根值。 4)短路冲击电流和冲击电流有效值: 短路冲击电流:短路全电流的最大瞬时值. 出现在短路后半个周期,t= ksh 为短路电流冲击系数;对于纯电阻电路,取1; 对于纯电感性电路,取2;因此,介于1和2之间。 冲击电流有效值:短路后第一个周期的短路全电流有效值。 5)稳态短路电流有效值: 短路电流非周期分量衰减后的短路电流有效值 p pm I I =p I == 0np pm p i I ≈ = ''p I I I == 0.01 (0.01)(0.01)(1)sh p np p sh p i i i e I τ - =+=+=sh sh p I I ==或 p I I ∞=''p k I I I I ∞====

6)三相短路容量: 短路电流计算步骤 短路等效电路图 短路电流计算方法 相对单位制法——标幺值法 概念:用相对值表示元件的物理量 步骤: 选定基准值 基准容量、基准电压、基准电流、基准阻抗 且有 通常选定Ud 、=100MVA,Ud=Uav= 3 K av K S U I =(,,,) (,,,)MVA kV kA MVA kV kA Ω=Ω物理量的有名值标幺值物理量的基准值d S d I d Z d U 33d d d d d d S U I U I Z ==2/(3)/d d d d d d I S U Z U S ?==

最短路径算法及其应用

湖北大学 本科毕业论文(设计) 题目最短路径算法及其应用 姓名学号 专业年级 指导教师职称 2011年 4月 20 日

目录 绪论 (1) 1 图的基本概念 (1) 1.1 图的相关定义 (1) 1.2 图的存储结构 (2) 1.2.1 邻接矩阵的表示 (2) 1.2.2 邻接矩阵的相关结论 (3) 2 最短路径问题 (3) 2.1 最短路径 (4) 2.2 最短路径算法 (4) 2.2.1Dijkstra算法 (4) 2.2.2Floyd算法 (5) 3 应用举例 (5) 3.1 Dijkstra算法在公交网络中的应用 (5) 3.1.1 实际问题描述 (5) 3.1.2 数学模型建立 (5) 3.1.3 实际问题抽象化 (6) 3.1.4 算法应用 (6) 3.2 Floyd算法在物流中心选址的应用 (7) 3.2.1 问题描述与数学建模 (7) 3.2.2 实际问题抽象化 (7) 3.2.3 算法应用 (8) 参考文献 (10) 附录 (11)

最短路径算法及其应用 摘要 最短路径算法的研究是计算机科学研究的热门话题,它不仅具有重要的理论意义,而且具有重要的实用价值。最短路径问题有广泛的应用,比如在交通运输系统、应急救助系统、电子导航系统等研究领域。最短路径问题又可以引申为最快路径问题、最低费用问题等,但它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra和Floyd算法是目前最短路径问题采用的理论基础。本文主要对Dijkstra和Floyd算法进行阐述和分析,然后运用这两个算法解决两个简单的实际问题。 【关键字】最短路径 Dijkstra算法 Floyd算法图论

最短路问题及其应用——最短路径

大连海事大学 图论论文 姓名: 学号: 专业:计算机科学与技术 院系:信息科学技术2009级

摘要: 主要介绍最短路的两种算法,迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。以及这两种算法在实际问题中的应用和比较。 关键字:图论,最短路径,树,生成树,迪杰斯特拉(Dijkstra),弗罗伊德(Floyd)算法

最短路问题及其应用 1 引言 图论是应用数学的一个分支,它的概念和结果来源非常广泛,最早起源于一些数学游戏的难题研究,如欧拉所解决的哥尼斯堡七桥问题,以及在民间广泛流传的一些游戏难题,如迷宫问题、博弈问题、棋盘上马的行走路线问题等.这些古老的难题,当时吸引了很多学者的注意.在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿(环游世界)数学难题. 1847年,图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学的发展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等各个领域的问题时,发挥出越来越大的作用.在实践中,图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2 最短路 2.1 最短路的定义 w≥对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图()0 ij 的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因

相关主题