最短路算法

我写的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 i=1:m

if dd(i)==0

d(i)=min(d(i),d(y)+D(y,i));

end

end

ddd=inf;

for i=1:m

if dd(i)==0&&d(i)

ddd=d(i);

end

end

yy=find(d==ddd);

counter=counter+1;

DD(y,yy(1,1))=counter;

DD(yy(1,1),y)=counter;

y=yy(1,1);

dd(1,y)=1;

end

function[D,R]=floyd(a)

n=size(a,1);

D=a

for i=1:n

for j=1:n

R(i,j)=j;

end

end

R

for k=1:n for i=1:n for j=1:n

if D(i,k)+D(k,j)

例9 某公司在六个城市621,,,c c c 中有分公司，从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。

????????

??????????∞

∞∞∞∞∞055

25

25

10

550102025251001020402010015252015050102540500

用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量pb 、1index 、2

index

、

d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量

??

?=顶点未标号

当第顶点已标号当第i i i pb 0

1

)(；

)(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号；

)(i d 存放由始点到第i 点最短通路的值。

求第一个城市到其它城市的最短路径的Matlab 程序如下： clear; clc;

M=10000;

a(1,:)=[0,50,M,40,25,10];

a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M];

a(4,:)=[zeros(1,4),10,25];

a(5,:)=[zeros(1,5),55];

a(6,:)=zeros(1,6);

a=a+a';

pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1;

while sum(pb)

tb=find(pb==0);

d(tb)=min(d(tb),d(temp)+a(temp,tb));

tmpb=find(d(tb)==min(d(tb)));

temp=tb(tmpb(1));

pb(temp)=1;

index1=[index1,temp];

index=index1(find(d(index1)==d(temp)-a(temp,index1)));

if length(index)>=2

index=index(1);

end

index2(temp)=index;

end

d, index1, index2

Floyd算法的Matlab程序如下：

clear;

clc;

M=10000;

a(1,:)=[0,50,M,40,25,10];

a(2,:)=[zeros(1,2),15,20,M,25];

a(3,:)=[zeros(1,3),10,20,M];

a(4,:)=[zeros(1,4),10,25];

a(5,:)=[zeros(1,5),55];

a(6,:)=zeros(1,6);

b=a+a';path=zeros(length(b));

for k=1:6

for i=1:6

for j=1:6

if b(i,j)>b(i,k)+b(k,j)

b(i,j)=b(i,k)+b(k,j);

path(i,j)=k;

end

end

end

end

b, path

6.3.2 旅行商（TSP ）问题

一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。

一个可行的办法是首先求一个Hamilton 圈C ，然后适当修改C 以得到具有较小权的另一个Hamilton 圈。修改的方法叫做改良圈算法。设初始圈121v v v v C n =。

（i ）对于n j i <<+<11，构造新的Hamilton 圈: 12112121v v v v v v v v v v v C n j j i j j j i ij +++--=,

它是由C 中删去边1+i i v v 和1+j j v v ，添加边j i v v 和11++j i v v 而得到的。若

)()()()(1111+++++<+j j i i j i j i v v w v v w v v w v v w ，则以ij C 代替C ，ij C 叫做C 的改良圈。

（ii ）转（i ），直至无法改进，停止。

用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。

这个算法的优劣程度有时能用Kruskal 算法加以说明。假设C 是G 中的最优圈。则对于任何顶点v ，v C -是在v G -中的Hamilton 轨，因而也是v G -的生成树。由此推知：若T 是v G -中的最优树，同时e 和f 是和v 关联的两条边，并使得)()(f w e w +尽可能小，则

)()()(f w e w T w ++将是)(C w 的一个下界。

这里介绍的方法已被进一步发展。圈的修改过程一次替换三条边比一次仅替换两条边更为有效；然而，有点奇怪的是，进一步推广这一想法，就不利了。

例13 从北京（Pe ）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：

clc,clear

a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60; a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70; a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61;

a(5,6)=13;

a(6,:)=0;

a=a+a';

c1=[5 1:4 6];

L=length(c1);

flag=1;

while flag>0

flag=0;

for m=1:L-3

for n=m+2:L-1

if

a(c1(m),c1(n))+a(c1(m+1),c1(n+1))

flag=1;

c1(m+1:n)=c1(n:-1:m+1);

end

end

end

end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1));

end

circle=c1;

sum=sum1;

c1=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动

flag=1;

while flag>0

flag=0;

for m=1:L-3

for n=m+2:L-1

if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...

a(c1(m),c1(m+1))+a(c1(n),c1(n+1))

flag=1;

c1(m+1:n)=c1(n:-1:m+1);

end

end

end

end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1));

end

if sum1

sum=sum1;

circle=c1;

end

circle,sum

用Kruskal算法构造例3的最小生成树

Matlab程序如下：

clc;clear;

M=1000;

a(1,2)=50; a(1,3)=60;

a(2,4)=65; a(2,5)=40;

a(3,4)=52;a(3,7)=45;

a(4,5)=50; a(4,6)=30;a(4,7)=42;

a(5,6)=70;

[i,j]=find((a~=0)&(a~=M));

b=a(find((a~=0)&(a~=M)));

data=[i';j';b'];index=data(1:2,:); loop=max(size(a))-1;

result=[];

while length(result)

temp=min(data(3,:));

flag=find(data(3,:)==temp);

flag=flag(1);

v1=data(1,flag);v2=data(2,flag);

if index(1,flag)~=index(2,flag) result=[result,data(:,flag)];

end

if v1>v2

index(find(index==v1))=v2;

else

index(find(index==v2))=v1;

end

data(:,flag)=[];

index(:,flag)=[];

end

result

最短路算法[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/6618517223.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． [６] 孙魁明、张海彤．Mathematica工具软件大全．北京：中国铁道出版社，1994． [７] 楼顺天、于卫、闫华梁．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 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因