堆在最短路中的应用

数据结构在单源最短路中的应用

【问题描述】：

给定图G(V,E)，求从源s到各个点的最短路长度。

【输入格式】：

第一行3个数n,m,k。

【问题分析】：

用Dijkstra求单源最短路。

【算法设计】：

Procedure Dijkstra;

S:={};

dist(s):=0;

dist(V-s):=MaxValue;

Insert(s);

For i:=2 to n do

Extarct-Min(x), x not in S;

S:=S+{x};

For all edge(x,y)∈G(V,E)

If dist(x)+weigh(x,y)

If dist(y)=MaxValue then

Insert(y);

Else

RelaxDist(y);

End For;

End Dijkstra.

使用线形表储存dist值，Insert与RelaxDist直接修改表中数值，复杂度O(1)，Extarct-Min 需要遍历整个表，复杂度O(n)，总复杂度O(n2)。

【算法优化】：

Dijkstra使用的数据结构需要不断更新或插入储存的值，同时能够取得最小值。堆是满足以上要求且不会退化的较好数据结构。

堆，是一种特殊的森林，对于森林中的所有非叶结点，它的子结点必然比它大。树根层是无序的并有指针min[H]指向最小的根结点（同时也是堆中最小结点）。堆支持的操作有：

z插入(Insert)：把待插入结点插入树根层一端，标记为空，复杂度O(1)

z取最值(Extarct-Min)：取min[H]指向的结点之后进行整理，不断合并根结点度数相同的树（根的值较小的作为父亲，清除合并进来的结点标记）直到没有两个根结点度数相同，复杂度O(lg n)。

z修改(Decrease-key)：减少结点值后移动(cut)到树根层一端，若父结点已标记继续移动，移动后清除自身标记，否则打上标记，循环直到已达到树根层或父结点原先没有标记，复杂度O(1)。

z删除(Delete)：将待删除结点的子结点移至树根层再进行与Extarct-Min相同的整理，复杂度O(lg n)。

【复杂度分析】：

用堆储存dist值，RelaxDist必然减小节点dist值，只需调用堆的Decrease-key过程与Insert复杂度同为O(1)，Extarct-Min复杂度O(lg n)，Insert和RelaxDist最多调用|E|次，Extarct-Min调用|V|次，总复杂度O(|E|+|V|lg|V|)。

【参考程序】：

program SSSP;

const

maxn=1000;

maxd=20;

maxvalue=maxlongint;

filein='';

fileout='';

type

Tindex=integer;

Tdatum=integer;

Tedge=object

w:Tdatum;

v:Tindex;

end;

Tedge2=object(Tedge)

u:Tindex;

end;

Plist=^Tlist;

Ttree=record

v,d:Tindex;

mark:boolean;

list,p:Plist

end;

Tlist=record

cl:Ttree;

next,prev:Plist

end;

Tnode=record

d:Tdatum;

index:Tindex;

checked:boolean;

pos:Plist

end;

Theap=object

function insert(pos:Tindex):Plist;

procedure deckey(pos:Plist);

function extract_min:Tindex;

procedure delete(pos:Plist);

private

root,min:Plist;

function makep(p,c:Plist):Plist;

procedure cut(pos:Plist);

procedure extract(pos:Plist);

end;

var

n,m,s,t:Tindex;

g:array[1..maxn*maxn]of Tedge;

nodes:array[0..maxn]of Tnode;

heap:Theap;

function Theap.insert(pos:Tindex):Plist;

var temp:Plist;

begin

new(temp);

insert:=temp;

temp.cl.v:=pos;

if (min=nil)or(nodes[pos].d

temp.cl.d:=0;

temp.cl.mark:=false;

temp.next:=root;

if root<>nil then

root.prev:=temp;

root:=temp;

root.prev:=nil

end;

function Theap.makep(p,c:Plist):Plist;

begin

if c.prev<>nil then

c.prev.next:=c.next;

if c.next<>nil then

c.next.prev:=c.prev;

if root=c then

root:=root.next;

c.prev:=nil;

c.cl.p:=p;

c.cl.mark:=false;

c.next:=p.cl.list;

if p.cl.list<>nil then

p.cl.list.prev:=c;

p.cl.list:=c;

inc(p.cl.d);

makep:=p

end;

procedure Theap.cut(pos:Plist);

var temp:Plist;

begin

repeat

dec(pos.cl.p.cl.d);

if pos.prev<>nil then

pos.prev.next:=pos.next;

if pos.next<>nil then

pos.next.prev:=pos.prev;

if pos.cl.p.cl.list=pos then

pos.cl.p.cl.list:=pos.cl.p.cl.list.next; pos.cl.mark:=false;

pos.next:=root;

root.prev:=pos;

root:=pos;

pos.cl.p.cl.mark:=not(pos.cl.p.cl.mark); temp:=pos;

pos:=pos.cl.p;

temp.cl.p:=nil;

until (pos.cl.mark=true)or(pos.cl.p=nil);

if pos.cl.p=nil then

pos.cl.mark:=false

end;

procedure Theap.extract(pos:Plist);

var

temp:Plist;

a:array[0..maxd]of Plist;

begin

while pos<>nil do

begin

temp:=pos.next;

pos.next:=root;

root.prev:=pos;

root:=pos;

pos:=temp

end;

root.prev:=nil;

fillchar(a,sizeof(a),0);

if root=min then

root:=root.next;

if root=nil then

exit;

pos:=root;

min:=root;

a[root.cl.d]:=root;

while pos.next<>nil do

begin

pos:=pos.next;

if a[pos.cl.d]<>nil then

begin

repeat

if nodes[temp.cl.v].d

else

temp:=makep(a[temp.cl.d],temp);

a[temp.cl.d-1]:=nil;

until a[temp.cl.d]=nil;

a[temp.cl.d]:=temp

end

else

a[pos.cl.d]:=pos;

if nodes[pos.cl.v].d

min:=pos

end

end;

procedure Theap.deckey(pos:Plist);

begin

if nodes[pos.cl.v].d

min:=pos;

if pos.cl.p<>nil then

cut(pos)

end;

function Theap.extract_min:Tindex;

begin

extract_min:=min.cl.v;

if min.prev<>nil then

min.prev.next:=min.next;

if min.next<>nil then

min.next.prev:=min.prev;

extract(min.cl.list)

end;

procedure Theap.delete(pos:Plist);

begin

if pos.cl.p<>nil then

if pos.cl.p.cl.mark then.

cut(pos.cl.p).

else

pos.cl.p.cl.mark:=true;

if pos.prev<>nil then

pos.prev.next:=pos.next;

if pos.next<>nil then.

pos.next.prev:=pos.next;

if pos=root then

extract(pos.cl.list)

end;

procedure init;

var

i:Tindex;

nt:array[0..maxn]of Tindex;

gt:array[1..maxn*maxn shr 1]of Tedge2;

begin

fillchar(nt,sizeof(nt),0);

fillchar(nodes,sizeof(nodes),0);

readln(n,m,s,t);

for i:=1 to m do

begin

read(gt[i].u,gt[i].v,gt[i].w);

inc(nt[gt[i].u]);

inc(nt[gt[i].v])

end;

for i:=1 to n do

begin

inc(nt[i],nt[i-1]);

nodes[i].index:=nt[i]

end;

for i:=1 to m do

begin

g[nt[gt[i].u]].v:=gt[i].v;

g[nt[gt[i].u]].w:=gt[i].w;

g[nt[gt[i].v]].v:=gt[i].u;

g[nt[gt[i].v]].w:=gt[i].w;

dec(nt[gt[i].u]);

dec(nt[gt[i].v])

end

end;

function main:Tindex;

var

i,j,e:Tindex;

begin

for i:=1 to n do

nodes[i].d:=maxvalue;

nodes[s].d:=0;

nodes[s].checked:=true;

for i:=nodes[s-1].index+1 to nodes[s].index do begin

nodes[g[i].v].d:=g[i].w;

nodes[g[i].v].pos:=heap.insert(g[i].v)

end;

for i:=2 to n do

begin

e:=heap.extract_min;

if e=t then

break;

nodes[e].checked:=true;

for j:=nodes[e-1].index+1 to nodes[e].index do if not nodes[g[j].v].checked then

if nodes[g[j].v].d>nodes[e].d+g[j].w then

begin

nodes[g[j].v].d:=nodes[e].d+g[j].w;

if nodes[g[j].v].pos=nil then

nodes[g[j].v].pos:=heap.insert(g[j].v) else

heap.deckey(nodes[g[j].v].pos)

end

end;

main:=nodes[t].d

end;

begin

assign(input,filein);

reset(input);

assign(output,fileout);

rewrite(output);

init;

writeln(main);

close(input);

close(output)

end.

最短路算法[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.wendangku.net/doc/be18215148.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表示问题的规模（象素个数）

最短路问题的实际应用论文

金华双龙洞旅游路线中最短路问题 摘要： 金华双龙洞景点分布较多，通过对其旅游路线的设置，转化为图论内容中的最短路情景进行讨论，建立模型，并通过搜索资料，利用几种方法解决路线最小的问题。 关键字： 数学建模最短路问题 lingo Dijkstra法 flod算法 一、研究背景： 在旅游过程中，我们常常感觉到自己一天下来走了很多路，回到宾 馆脚痛的不行。但其实我们可以利用运筹学的知识，通过建立数学 模型，转化为图论的内容。从而较为合理的制定出选择的路线（即 最短路问题）。 因而这次的小论文，我主要探究一下几个问题： 1.从景点进口到出口的最短路程。（最短路问题） 2.从景点到出口的最长路线。 3.建立的模型是否满足能回到起点（古典图论问题） 二、研究内容： 根据从互联网中搜索的资料，金华双龙洞的主要景点：景区进口双 龙洞，冰壶洞，朝真洞，桃源洞，黄大仙祖宫五个，其余为小景点 （若要加入，同样可以按照以下问题的研究方法进行讨论）现在忽 略。 问题总假设：分别设置双龙洞，冰壶洞，朝真洞，桃源洞，黄大仙 祖宫五个景点为A,B,C,D,E五点，根据现实及假设，可以得到如图 所示的路线图：

再利用用Dijkstra算法求解无负权网络的最短路。同时也可以利用此法算出最长路程。 问题一的解决：以A为景点出口，E为出口。 故A点标号为P（a）=0 给其余所有的T标号T（i）=+∞ 考虑与A相邻的两个顶点BC，两个顶点为T标号，故修改这两个点的标号为：T(b)=min[T(b),P(a)+l12]=min[+∞,0+3]=3 T(c)=min[T(c),P(a)+l13]=min[+∞,0+2]=2 比较所有T标号，T(c)最小，所以令P(c)=2 再考察（C,B）(C,D)(C,E)的端点：同理可得 T(b)=6 T(d)=6.8 T(e)=10.2(显然已经到终点但还需要看看其余路线长短) 故又令P（b）=6.综合分析只有一条线路即A→C→B→D→E 此时总路程为2+4+3+8.4=16.4>10.2 所以，最短路程为A→C→E。即当游客不想再看双龙洞时或者因为脚伤等因素需以最小路程离开时，可以路线A→C→E离开景区。 特殊情况的处理：游客一定要去B景点则在一开始就应该先选择 B，而非C。才能使路线最短。因此，对于特殊问题，我们应当具体 问题，具体分析。

浅谈断路和短路故障及应用

浅谈断路和短路故障及应用 自从人类发明发电机以来，电给人们的生活带来了许许多多的方便，直至今天，人们的生活已经离不开电，电成为我们生活中不可缺少的东西，它能给我们带来光明，舒适和欢乐。 标签：电路短路断路故障控制应用 电的使用是和我们日常生活中的用电器联系在一起的，比如灯泡照明、电视机播放录像、电冰箱储藏食品等等，而这些用电器的使用都离不开电路，所以电路的知识和我们的生活是息息相关的。在我们使用这些用电器的时候，有时电路会出现故障导致用电器无法正常使用，这就需要我们进行电路分析，找出故障的原因，从而解决问题。而断路和短路现象是日常用电中经常出现的两种故障，一般来讲断路和短路都是我们所不希望的，即断路和短路都是不好的现象，但是事物都具有两面性，在有些时候，断路和短路对我们的生产和生活也有有利的一面，比如利用断电器和保险丝可以保护用电器，利用短路可以实现对用电器的控制等等。深入的探究断路和短路现象，对于我们的日常用电具有重要的现实意义。 一、何为断路，何为短路 二、断路和短路的特点分析。 1.断路特点：对于断路状态，电流为零，断开处的电压即为电源的电压。 由于断路状态下，整个电路在某处断开，所以在断开处导线连接的是空气，一般来讲空气是绝缘体，故电阻很大，所以断路状态下电路中的电流几乎为零，再根据分压关系，串联电路中元件的电阻与电压成正比，所以电压几乎都降落在断开处，即断开处两端的电压就等于电源的电压。 2.短路的特点：电路中如果将电源短路则由于回路中电阻几乎为零，故会在回路中产生很大的电流，进而会引起电源或者某部分电路发热烧毁电源或电路。如果是回路中某一个用电器被短路，则电流不会流过该用电器，用电器无法使用。我们可以用并联电路的特点来分析用电器的短路。 三、造成断路和短路的原因 断路的原因一般就是电路中某处断开，或是用电器自身损坏使电路断开。有时候短路也会造成断路，我们考虑如果一个电路中电源被短路，那么回路的电流会很大，从而电路严重发热，这将会导致烧毁电源，或电路中的用电器或是导线，从而使电路断开。 生活中造成线路中短路现象的原因有很多，主要有以下几个方面：

初中物理断路、短路分析

初中物理断路、短路分析

————————————————————————————————作者: ————————————————————————————————日期:

如何判断电路故障问题 “电路的故障”问题在中考时常出现在电路选择题中，它主要分为无电表（电流表、电压表）和有电表两种情况下的电路故障，电路故障主要包括断路和短路,造成断路的主要原因有:①连接电路时,导线与接线柱之间接触不良；②由于电压过高电路被烧断，比如灯被烧坏； ③将电压表串联在电路中,因为电压表的内阻过大,造成电压表所在电路断路。而造成短路的主要原因有:电路的错误连接产生短路，如电流表并联在电路中,因电流表的内阻太小，相当于接入了导线。现举例分析。 一. 无电表时的电路故障 例1. 小明在做实验时把甲、乙两灯泡串联后通过开关接在电源上,闭合开关后,甲灯发光，乙灯不发光。乙灯不发光的原因是（) A．它的电阻太小；B. 它的电阻太大；C. 流过乙灯的电流比甲灯小;D．乙灯灯丝断了。 分析与解答:因为甲、乙两灯组成的是串联电路,当开关闭合后，甲灯发光，这证明电路是通路,所以要想知道乙灯不亮的原因，必须得清楚串联电路的电流、电压及电阻的各自特点。因串联电路的电流处处相等,因此有串联电阻两端的电压与电阻是成正比关系的，当乙灯电阻太小时,其两端的电压也太小,远小于其额定电压，所以乙灯不会发光。 答案：A 二. 有电表时的电路故障 例2. 如图1所示为两个灯组成的串联电路，电源电压为6V,闭合开关Ｓ后 两灯均不发光，用一只理想电压表测量电路中aｂ间电压为0,bc间电压为 6V,则电路中的故障可能为: A. L1短路且L２断路Ｂ. L1和L2均断路Ｃ. L1断路且L2短路 D. 只有Ｌ2断路 分析与解答:本题主要考查电路发生故障原因的判断,解题关键是理解电路 的连接及特性。分析时可以从有示数的电表或有工作的用电器开始分析： ①当电压表接在ａb间时电压为0,说明电压表中无电流通过，即电压表、 电源、开关、灯Ｌ２组成的是开路;②当电压表接在bｃ间时电压为6V,说明 电压表中有持续的电流通过,即电压表、电源、开关、灯L1组成通路，这时 电压表示数接近电源电压为6Ｖ。③若L1短路,也为零,,但 L2应发光,与题目不符。答案:D 例3．如图２所示，闭合开关,两只灯泡都不亮，且电流表和电压表的指针都不动。现将两只灯泡L1和Ｌ2的位置对调，再次闭合开关时，发现两只灯泡仍不亮，电流表指针仍不动,但电压表的指针却有了明显的偏转，该电路的故障可能是( ) A．从a点经过电流表到开关这段电路中出现断路；B. 灯泡L1的灯丝断 了；C．灯泡L2的灯丝断了;Ｄ. 电流表和两个灯泡都坏了。 分析与解答：因为电流表指针不动,两灯都不亮，说明电路中没有电流通 过,电路应判断为断路。当L1、L2位置对调时，如图３所示:

图论及其应用(精)

图论及其应用 学时：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．教学具体内容 图的基本概念，路和圈，最短路问题。

电路中短路和断路的判断方法

电路中短路和断路的判断方法 1、先根据题给条件确定故障是断路还是短路：两灯串联时，如果只有一个灯不亮，则此灯一定是短路了，如果两灯都不亮，则电路一定是断路了；两灯并联，如果只有一灯不亮，则一定是这条支路断路，如果两灯都不亮，则一定是干路断路。在并联电路中，故障不能是短路，因为如果短路，则电源会烧坏。 2、根据第一步再判断哪部分断路或短路。 例1：L1与L2串联在电路中，电压表测L2两端电压，开关闭合后，发现两灯都不亮，电压表有示数，则故障原因是什么？解：你先画一个电路图：两灯都不亮，则一定是断路。电压表有示数，说明电压表两个接线柱跟电源两极相连接，这部分导线没断，那么只有L1断路了。 例2、L1与L2串联，电压表V1测L1电压，V2测L2电压。闭合开关后，两灯都不亮。则下列说法正确的是：A、若V1=0，V2示数很大，则L1短路而L2正常；B、若V1=0而V2示数很大，说明L2都断路。 解：可能你会错选A。其实答案为B。首先根据题给条件：两灯都不亮，则电路是断路，A肯定不正确。当L2断路时，此时V2相当于连接到了电源两极上，它测量的是电源电压，因此示数很大。而此时L1由于测有电流通过，因此两端没有电压，因此V1的示数为零。 再给你一个口诀 分析电路的口诀1、分析电路应有方法：先判串联和并联；电表测量然后断。一路到底必是串；若有分支是并联。2、还请注意以下几点：A表相当于导线；并时短路会出现。如果发现它并源；毁表毁源实在惨。若有电器被它并；电路发生

局部短。 V表可并不可串；串时相当电路断。 如果发现它被串；电流为零应当然。 连接电路口诀1、连接电路怎么办：串联很简单，各个元件依次连；并联有点难，连干路，标节点；支路可要条条连，连好再检验。2、还有电表怎样连：A 表串其中；V表并两端。线柱认真接；正(进)负(出)不能反。量程不能忘；大小仔细断。3、最后提醒你一点：无论串联或并联；电压表应最后连。

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

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

电学断路与短路习题

电学断路与短路习题 一?选择题（共10小题） 1 ?某同学使用手电筒时发现小灯泡不亮，在进行检修前，他对造成该现象的直 接原因进行了以下几种判断，其中不可能的是（ ） A. 小灯泡灯丝断了 B.电池两端电压过低 C 小灯泡接触不良 D .开关处出现短路 2 .灯泡L i 、L 2组成并联电路，闭合开关后L i 发光、L 2不发光.故障可能是（ ） A. L i 被短路 B. L i 所在支路断路 C. L 2被短路 D.匕所在支路断路 3. 如图所示的四个电路中，若将开关 S 闭合，会发生短路的电路是（ ） A . 4. 如图所示电路，当S i 、 S 2都闭合时，发光的灯是（ ） C. B 和C D .都发光 5. 如图所示，开关S 闭合后，会出现的现象是（ A . L i 与L 2都亮 B . L i 亮，L 2不亮 C . L i 不亮，L 2亮 D . L i 与L 2都不亮 6. — 种声光报警器的电路如图所示.闭合开关Sl 和S 2后，会出现的现象是（ ） B. L 亠 D.

A.灯亮，铃不响 B.灯不亮，铃不响 C灯亮，铃响D.灯不亮，铃响 7. 如图所示，闭合开关S时，灯泡L i、L2都不亮.用一段导线的两端接触 a、b 两点时，两灯都不亮；接触 b、C两点时，两灯都不亮；接触 c、d两点时，两灯都亮.则（）

LI tj L2 *~ I ---- ?― ------- H A.灯L i断路 B.灯L2断路C灯L2短路D.开关S断路 8. 下列说法中正确的是（） A. 电路中用电器过多一定会造成电路中电流过大 B. 开关闭合的电路一定是通路 C. 电路中开关被短路时电流会很大会造成事故 D. 电路中连接导线松脱会产生断路 9. 如图所示的三个电路，下列对其通路、开路、短路判断正确的是（ A.甲开路，乙通路，丙短路C甲通 路，乙短路，丙开路 IO.如图所示的电路中，闭合开关 Si、S U灯L i、L2两端电压均未超过其额定电压），下列说法中正确的是（） Ll 闭合开关Sp S2，灯L i亮、L2不亮闭合开关S、③，灯L i、L2都亮只闭合开关Si,灯L i亮、L2不亮只闭合开关S2,灯L i、L2都亮二.填空题（共5小题） II. 如图所示电路，若闭合开关，电路将—（选填通路” 开路” 短路”）, 这是不允许的，必须改正：若要使电路中的两灯串联，只要拆除导线—即可; 若要使电路中的两灯并联，则要改接导线—. C I2.如图所示电路，若使两灯并联，开关的闭合和断开情况是—；若同时闭合开关—，则会使电源被短路. 13. 理发用电吹风的典型电路如图所示，其中电热丝通电后可以发热，电动机M 通电后可以送风?选择开关放在热” 冷” 停”位置上，电动机可分别送出热风、冷风或处于停机状态，则1-2位置是_的位置；2-3的位置是_的位置；3-4位置是 的位置. —— B.甲短路，乙开路，丙通路 D.甲通路，乙开路，丙短路 A. B. C. D. Λ L2

最短路问题(整理版)

最短路问题(short-path problem) 若网络中的每条边都有一个权值值(长度、成本、时间等)，则找出两节点(通常是源节点与结束点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题（确定起点或确定终点的最短路径问题）、确定起点终点的最短路径问题（两节点之间的最短路径） 1、Dijkstra算法： 用邻接矩阵a表示带权有向图，d为从v0出发到图上其余各顶点可能达到的最短路径长度值，以v0为起点做一次dijkstra，便可以求出从结点v0到其他结点的最短路径长度 代码： procedure dijkstra（v0：longint）；//v0为起点做一次dijkstra begin//a数组是邻接矩阵，a[i,j]表示i到j的距离，无边就为maxlongint for i:=1 to n do d[i]:=a[v0,i];//初始化d数组（用于记录从v0到结点i的最短路径）， fillchar(visit,sizeof(visit),false);//每个结点都未被连接到路径里 visit[v0]:=true;//已经连接v0结点 for i:=1 to n-1 do//剩下n-1个节点未加入路径里； begin min:=maxlongint;//初始化min for j:=1 to n do//找从v0开始到目前为止，哪个结点作为下一个连接起点（*可优化） if (not visit[j]) and (min>d[j]) then//结点k要未被连接进去且最小 begin min:=d[j];k:=j;end; visit[k]:=true;//连接进去 for j:=1 to n do//刷新数组d，通过k来更新到达未连接进去的节点最小值， if (not visit[j]) and (d[j]>d[k]+a[k,j]) then d[j]:=a[k,j]+d[k]; end; writeln(d[n]);//结点v0到结点n的最短路。 思考：在实现步骤时，效率较低需要O(n)，使总复杂度达到O(n^2)。对此可以考虑用堆这种数据结构进行优化，使此步骤复杂度降为O(log(n))(总复杂度降为O(n log(n))。 实现：1. 将与源点相连的点加入堆（小根堆），并调整堆。 2. 选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。 3. 处理与u相邻（即下一个）未被访问过的，满足三角不等式的顶点 1):若该点在堆里，更新距离，并调整该元素在堆中的位置。 2):若该点不在堆里，加入堆，更新堆。 4. 若取到的u为终点，结束算法；否则重复步骤2、3。 **优化代码：(DIJKSTRA+HEAP) program SSSP;{single source shortest path} {假设一个图的最大节点数为1000，所有运算在integer范围内} {程序目标：给定有向图的邻接表，求出节点1到节点n的最短路径长度} const maxn=1000;{最大节点数} var n:integer;{节点个数} list:array[1..maxn,1..maxn] of integer;{邻接矩阵，表示边的长度}

短路和断路分析

一、断路的判断 1．断路的主要变现。断路最显著的特征是电路(并联的干路)中无电流（电流表无读数），且所有用电器不工作（常是灯不亮），电压表读数接近电源电压。如果发现这种情况，则电路的故障是发生了断路。2．判断的具体方式。采用小灯泡法、电压表法、电流表法、导线法等与电路的一部分并联。原理是在并联的部分断路时，用小灯泡法、电压表法、电流表法、导线法等与电路的一部分并联再造一条电流的路径，若这条路径搭在哪里使电路恢复通路，则与之并联的部分就存在断路。 （1）电压表检测法。把电压表分别和逐段两接线柱之间的部分并联，若有示数且比较大（常表述为等于电源电压），则和电压表并联的部分断路（电源除外）。电压表有较大读数，说明电压表的正负接线柱已经和相连的通向电源的部分与电源形成了通路，断路的部分只能是和电压表并联的部分。 （2）电流表检测法。把电流表分别与逐段两接线柱之间的部分并联，如果电流表有读数，其它部分开始工作，则此时与电流表并联的部分断路。注意，电流表要用试触法选择合适的量程，以免烧坏电流表。（3）导线检测法。将导线分别与逐段两接线柱之间的部分并联，如其它部分能开始工作，则此时与电流表并联的部分断路。 （4）小灯泡检测法。将小灯泡分别与逐段两接线柱之间的部分并联，如果小灯泡发光或其它部分能开始工作，则此时与小灯泡并联的部分断路。 二、短路的判断 较常见的是其中一个用电器发生局部短路。一个用电器两端电压突然变大，或两个电灯中突然一个熄灭，另一个同时变亮，或电路中的电流变大等。 1．短路的具体表现： （1）整个电路短路。电路中电表没有读数，用电器不工作，电源发热，导线有糊味等。 （2）串联电路的局部短路。某用电器（发生短路）两端无电压，电路中有电流（电流表有读数）且较原来变大，另一用电器两端电压变大，一盏电灯更亮等。 2．判断方法：短路情况下，是“导线”成了和用电器并联的电流的捷径，电流表、导线并联到电路中的检测方法已不能使用，因为，它们

初中物理短路断路专题

百度文库 电路故障专题 电路故障分析一直是电学主流的题型之一，中考中一般都会有体现，出现在选择、填空、或实验题中。考察对电表使用、电学实验操作常规的把握，及其运用电学知识解决实际电路问题的能力。 一般来说，造成电路故障的原因主要有元件的短路、短路两种。故障的原因与现象如图1所示。 上述电路中，分析等L 1、L 2、 电压表、电流表、开关处于短路或短路状态的时候，分析两个灯泡和电压表电流表的示数情况。 逆向思维练习 例1在如图所示的电路中，当闭合开关S 后，发现两灯都不亮，电流表的指针几乎指在“0”刻度线不动，电压表指针则有明显偏转，该电路中的故障可能是 A ．电流表被烧坏了 B ．灯泡L1的灯丝断了 C ．两个灯泡都断路 D ．灯泡L2的灯丝断了 例题2小星用图7.1.2所示的电路来探究串联电路的电压关系。已知电源电压为6V ，当开关S 闭合后，发现两灯均不亮。 电 路 故 障 灯泡 短路 原因：接线柱碰线 现象：灯泡不亮 断路 原因 接线柱接触不良 灯丝烧坏（断） 现象：灯泡不亮 电压表 短路 原因：接线柱碰线 现象：电压表无示数 断路 原因：接线柱接触不良或损坏 现象：电压表无示数 与用电 器串联 原因：与电压表并联的用电器断路 现象 电压表示数几乎等于电源电压 电路电流几乎为0不能使用电器正常工作 电流表 短路 原因：接线柱碰线 现象：电流表示数为0 断路 原因：接线柱接触不良，或电流表已烧坏 现象：电流表无示数 滑变 短路 原因 接线柱错接“一上，一上” 闭合开关前没有调节滑片p 位于“阻值最大处” 现象：起不到保护作用，电路电流很大 断路 原因：接线柱接触不良或烧坏 现象：整个电路被断开 接法错误，连入电阻最大并不改变 原因：接“一下，一下” 现象：阻值不变，较大 开关 短路：不存在，相当于开关闭合 断路：相当于开关断开 灯L 1发光情况 灯L 2发光情况 电流表示数情况 电压表示数情况 灯L 1短路 灯L 1断路 灯L 2短路 灯L 2断路 电压表短路 电压表断路 电流表短路 电流表、开关断 路

串并联电路的断路或短路故障

串并联电路的断路或短 路故障 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】

串联电路的断路或短路故障分析判断方法; 一、先根据题给条件确定故障是断路还是短路： (1)两灯串联时，如果只有一个灯不亮，则此灯一定是短路了，如果两灯 都不亮，则电路一定是断路了； 二、根据第一步再判断哪部分断路或短路。 1、电流表无示数----断路 （1）电压表示数为电源电压-------------与 电压表并联的电器断路 例如：L1与L2串联在电路中，电压表测L2两 端电压，开关闭合后，发现两灯都不亮，电压 表有示数，则故障原因是什么 分析: 两灯都不亮，则一定是断路。电压表有示数，说明电压表两个接线柱跟电源两极相连接，这部分导线没断，那么只有与电压表并联的电器断路L2断路了 （2）电压表无示数-------------电压表并联以外电路断路 例如：L1与L2串联，电压表V1测L1电压，V2测L2 电压。闭合开关后，两灯都不亮。则下列说法正确的 是：( ) A、若V1=0，V2示数很大，则L1短路而L2正常； B、若V1=0而V2示数很大，说明L2都断路。 解：首先根据题给条件：两灯都不亮，则电路是断路，A肯定不正确。

当V1=0,与V1并联的L1不断路， 当V2示数很大，则与V2并联的L2断路。 巩固：1、如图所示，闭合开关S后，L1和L2两盏电灯都 不亮，电流表指针几乎没有偏转，电压表指针明显偏转， 该电路的故障可能是（） A、L1灯丝断了 B、L2灯丝断了 C、电流表损坏 D、L2灯口处短路 2 、电流表有示数（或变大）-----------短路 （1）电压表示数为电源电压（或变大）----------电压表并联以外电路短路 例1：在如右图所示电路中，电源电压不变。闭 合开关S，电路正常工作。过了一会儿，两电表 的示数都变大，则该电路中出现的故障可能是 （） A．灯L断路 B、灯L短路 C、电阻R断路 D、电阻R短路 例2 、如图所示的电路中，电源电压为6伏。当 开关K闭合时，只有一只灯泡发光，且电压表V 的示数为6伏。产生这一现象的原因可能是 ( )

(word完整版)初中物理短路断路专题

电路故障专题 电路故障分析一直是电学主流的题型之一，中考中一般都会有体现，出现在选择、填空、或实验题中。考察对电表使用、电学实验操作常规的把握，及其运用电学知识解决实际电路问题的能力。 一般来说，造成电路故障的原因主要有元件的短路、短路两种。故障的原因与现象如图1所示。 上述电路中，分析等L 1、L 2、 电压表、电流表、开关处于短路或短路状态的时候，分析两个灯泡和电压表电流表的示数情况。 逆向思维练习 例1在如图所示的电路中，当闭合开关S 后，发现两灯都不亮，电流表的指针几乎指在“0”刻度线不动，电压表指针则有明显偏转，该电路中的故障可能是 A ．电流表被烧坏了 B ．灯泡L1的灯丝断了 C ．两个灯泡都断路 D ．灯泡L2的灯丝断了 例题2小星用图7.1.2所示的电路来探究串联电路的电压关系。已知电源电压为6V ，当开关S 闭合后，发现两灯均不亮。他用电压表分别测a 、c 和a 、b 两点间的电压，发现两次电压表示数均为6V ，由此判定灯_______（选填“L 1”或“L 2”）开路，用电压表测b 、c 两点间的电压，示数为_______V 。 电 路 故 障 灯泡 短路 原因：接线柱碰线 现象：灯泡不亮 断路 原因 接线柱接触不良 灯丝烧坏（断） 现象：灯泡不亮 电压表 短路 原因：接线柱碰线 现象：电压表无示数 断路 原因：接线柱接触不良或损坏 现象：电压表无示数 与用电 器串联 原因：与电压表并联的用电器断路 现象 电压表示数几乎等于电源电压 电路电流几乎为0不能使用电器正常工作 电流表 短路 原因：接线柱碰线 现象：电流表示数为0 断路 原因：接线柱接触不良，或电流表已烧坏 现象：电流表无示数 滑变 短路 原因 接线柱错接“一上，一上” 闭合开关前没有调节滑片p 位于“阻值最大处” 现象：起不到保护作用，电路电流很大 断路 原因：接线柱接触不良或烧坏 现象：整个电路被断开 接法错误，连入电阻最大并不改变 原因：接“一下，一下” 现象：阻值不变，较大 开关 短路：不存在，相当于开关闭合 断路：相当于开关断开 灯L 1发光情况 灯L 2发光情况 电流表示数情况 电压表示数情况 灯L 1短路 灯L 1断路 灯L 2短路 灯L 2断路 电压表短路 电压表断路 电流表短路 电流表、开关断 路 电路故障分析

电路短路断路练习

1 电路的断路、短路故障分析 电路的断路或局部短路故障判断是一类重要的能力题目，历年考试均加以了强调，这类题目涉及了电路连接方式、电流定律和串、并联电路的特点等知识，同时还要具备一定的分析、推理能力。 一、 串联电路的断路或局部短路故障现象如下表： 内容 断路 局部短路 实质 某电阻（或导线）变为阻值无穷大。 某电阻值变为0，可看作一根导线。 电流情况 电路中（任何处）均无电流。 短路处无电流，整个电路中电流变大。 用电器工作情况 均不工作。 有一个工作，另一个不工作。 故障发生处 电路中任何一点。 只可能在电阻上。 电流表的示数 无示数。 有示数且变大。 电压表的示数 断路处两端电压为电源电压，其余部分为0。 短路处为0，仍然工作的用电器（电阻）两端电压为电源电压。 串联电路的断路或短路故障分析，一般先判断电路中是否有电流（或用电器是否均工作），以确定故障到底是短路还是断路；然后可根据电压情况来判断故障发生的地方。 1、如图所示电路，电源电压不变。闭合电键，灯L 1和L 2都发光。一段时间后，其中的一盏灯突然熄灭，而电压表V 1的示数变大，电压表V 2的示数变小，则产生这一现象的原因是（ ） A 、灯L 1断路。 B 、灯L 2断路。 C 、灯L 1短路。 D 、灯L 2短路。 2、某同学正在做“用滑动变阻器控制灯的亮度”的实验。实验时电路出现的现象和电压表的示数如图所示，则电路出现的故障可能是（ ） A 、电池没电了。 B 、电键处有断路。 C 、灯丝断路。 D 、滑动变阻器处有断路。 3、如图所示，将两只灯泡串联在电路中，闭合电键后，发现其中一只灯亮，一只灯不亮。发生这种现象的原因是 （ ） A 、不亮的灯泡灯丝断了或接触不良。 B 、两灯比较，不亮的灯泡电阻太大。 C 、两灯比较，不亮的灯泡电阻太小。 D 、两灯比较，通过不亮的灯泡的电流较小。 4、如图所示电路，电源电压不变。闭合电键，电路正常工作。一段时间后，发现两个电压表的示数相等，则 （ ） 第1题图 第2题图 第3题图 第4题图

最短路径问题的反思及应用

《最短路径问题》的反思及应用 我们知道，有效地开发和利用课本，对于学生的学习具有重要的意义。学生对于课本上例题或习题能否吃透，直接影响着学生的学习效果。因此教师要引导学生挖掘教材，引导学生进行反思，从中领悟问题解决过程的数学内涵。 有这样一个问题： 如图1所示，牧马人从A 地出发，到一条笔直的河边l 饮马，然后到B 地。牧马人到河边的什么地方饮马，可使所走的路径最短? 分析 我们把河边近似看做一条直线l (如图2)，P 为直线l 上的一个动点，那么，上面的问题可以转化为：当点P 在直线l 的什么位置时，AP 与PB 的和最小。 如图3所示，作点B 关于直线l 的对称点'B ，连接'AB ，交直线l 于点P ，则点P 就是牧马人到河边饮马的位置。事实上，点'B 与点A 的线段'AB 最短，由对称性质知，'PB PB =，因为''PA PB PA PB AB +=+=，即点P 到点A 、B 的距离之和最小。 上述路径问题，是利用轴对称的性质，通过等线段代换，将所求路线长转化为两定点之间的距离，基本思路是运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长。从解题过程不难看出，本题蕴含着三个数学思想方法:数学模型思想，转化思想，对称思想。如果学生一旦认识或明白这些思想方法，就能举一反三，再复杂的问题也会迎刃而解。 一、基本应用 如图4，点O 是矩形ABCD 的中心，E 是AB 上的点，沿CE 折叠后，点B 恰好与点O 重合，若3BC =，则折痕CE 的长为多少? 分析 沿CE 折叠后，点B 恰好与点O 重合，则点B 、点O 关于直线CE 对称， 3CO CB ==，1122 ACB ∠=∠=∠，点O 是矩形ABCD 的中心，知26AC CO ==。所以12302 ACB ∠=∠=?，又在Rt CBE ∠中，30BCE ∠=?，3BC =，若设BE x =，则 2CE x =，得222(2)3x x -=，13x =23x -（舍去），所以223CE x == 二、拓展应用 如图5两条公路BA 、BC 相交于点B ，在两条公路之间的P 点有一个油库，若要在公

(完整)初中物理断路、短路分析

如何判断电路故障问题 “电路的故障”问题在中考时常出现在电路选择题中，它主要分为无电表（电流表、电压表）和有电表两种情况下的电路故障，电路故障主要包括断路和短路，造成断路的主要原因有：①连接电路时，导线与接线柱之间接触不良；②由于电压过高电路被烧断，比如灯被烧坏；③将电压表串联在电路中，因为电压表的内阻过大，造成电压表所在电路断路。而造成短路的主要原因有：电路的错误连接产生短路，如电流表并联在电路中，因电流表的内阻太小，相当于接入了导线。现举例分析。 一. 无电表时的电路故障 例1. 小明在做实验时把甲、乙两灯泡串联后通过开关接在电源上，闭合开关后，甲灯发光，乙灯不发光。乙灯不发光的原因是（） A. 它的电阻太小； B. 它的电阻太大； C. 流过乙灯的电流比甲灯小； D. 乙灯灯丝断了。 分析与解答：因为甲、乙两灯组成的是串联电路，当开关闭合后，甲灯发光，这证明电路是通路，所以要想知道乙灯不亮的原因，必须得清楚串联电路的电流、电压及电阻的各自特点。因串联电路的电流处处相等，因此有串联电阻两端的电压与电阻是成正比关系的，当乙灯电阻太小时，其两端的电压也太小，远小于其额定电压，所以乙灯不会发光。 答案：A 二. 有电表时的电路故障 例2. 如图1所示为两个灯组成的串联电路，电源电压为6V，闭合开关S 后两灯均不发光，用一只理想电压表测量电路中ab间电压为0，bc间电压 为6V，则电路中的故障可能为： A. L1短路且L2断路 B. L1和L2均断路 C. L1断路且L2短路 D. 只有L2断路 分析与解答：本题主要考查电路发生故障原因的判断，解题关键是理解电 路的连接及特性。分析时可以从有示数的电表或有工作的用电器开始分析： ①当电压表接在ab间时电压为0，说明电压表中无电流通过，即电压表、 电源、开关、灯L2组成的是开路；②当电压表接在bc间时电压为6V，说明 电压表中有持续的电流通过，即电压表、电源、开关、灯L1组成通路，这 时电压表示数接近电源电压为6V。③若L1短路，也为零，， 但L2应发光，与题目不符。答案：D 例3. 如图2所示，闭合开关，两只灯泡都不亮，且电流表和电压表的指针都不动。现将两只灯泡L1和L2的位置对调，再次闭合开关时，发现两只灯泡仍不亮，电流表指针仍不动，但电压表的指针却有了明显的偏转，该电路的故障可能是（） A. 从a点经过电流表到开关这段电路中出现断路； B. 灯泡L1的灯丝断 了；C. 灯泡L2的灯丝断了；D. 电流表和两个灯泡都坏了。 分析与解答：因为电流表指针不动，两灯都不亮，说明电路中没有电流通 过，电路应判断为断路。当L1、L2位置对调时，如图3所示： 电压表有示数，说明电压表的两端一定和电源连通，即电流从电源正极经

最短路问题在运输网络中的应用

第25卷第3期 Vol .25　No .3长春师范学院学报(自然科学版)Journal of Changchun Normal University (Natural Science )2006年6月Jun .2006 最短路问题在运输网络中的应用 李　玲 (陕西工业职业技术学院,陕西咸阳　712000) [摘　要]最短路问题是在图的基础上衍生出来的,也是网络优化中的一个基本问题,许多选择优化 问题都可以转化为最短路问题来求解。本文重在研究公路网络运输中的最短路问题。 [关键词]最短路;网络运输;网络优化;动态规划 [中图分类号]O221 [文献标识码]A [文章编号]1008-178X (2006)03-0058-04 [收稿日期]2006-02-01 [作者简介]李　玲(1977-),女,陕西商洛人,陕西工业职业技术学院教师,从事计算机专业基础课教学研究。 1　最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图(w ij ≥0)的有效算法是由荷兰著名计算机专家E .W .Dijkstra [1]在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解 图G 中一特定点到其它各顶点的最短路。后来海斯[2]在Dijkstra 算法的基础之上提出了海斯算法。但这两种 算法都不能解决含有负权的图的最短路问题。因此由Ford [3]提出了Ford 算法,它能有效地解决含有负权的最 短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在(w ij ≥0)的情况下选择Dijkstra 算法。 定义1[4]若图G =G (V ,E )中各边e 都赋有一个实数W (e ),称为边e 的权,则称这种图为赋权图,记为G =G (V ,E ,W )。 定义2[5] 若图G =G (V ,E )是赋权图且W (e )≥0,e ∈E (G ),若u 是v i 到v j 的路W (u )的权,则称W (u )为u 的长,长最小的v i 到v j 的路W (u )称为最短路。 若要找出从v 1到v n 的通路u ,使全长最短,即min W (u )=∑e ij ∈u W (e )。2　最短路问题算法的基本思想及基本步骤 在诸多算法中(w ij ≥0)最经典的算法当属Dijkstra 算法,该算法的基本思想是动态规划[6]最优原理,即最短路线上任意两点间的路线也是最短。因此,若v i 到v j 的最短路线经过v k ,则v i 到v k 以及v k 到v j 的部分都是相应的最短路线。 基本步骤: 令 s ={v 1},i =1, s ={v 2,v 3,…,v n } 并令 W (v 1)=0 T (v j )=∞,v j ∈ s ①对v j ∈ s ,求min {T (v j ),W (v i )+w ij }=T (v j )。 ②求min v j ∈ s {T (v j )}得T (v k ),使T (v k )=min v j ∈ s {T (v j )}