刘大中 客座教授
摘要
本文介绍了CAD（Computer Aid Design）中关键的最短路及最长路算法，其应用于电路分析中简便易行；已用C语言编写程序，正确解题。
A＞前言
众所周知，在对电路进行分析设计过程中，一定要涉及路径及时间的问题，其中就一定要采用最短路径及最长路径的算法，对复杂的电路进行自动跟踪分析，本文对有向各G=（V,E）中，各边加权（重量）为非负值时的某一指定点（S）到其它各点间的最短路径及最长路径进行讨论，给出通用算法，并对该算法进行分析、设计，最后用C语言编写程序。结果表明，本文采用的算法简便易行、效率高、可靠性好。
B＞最短路径算法
一、算法
begin
1 T←Ø
2 X←V－〔s〕；
3 distance(s)←O；
4 for each x in X do
5 if (s,x)∈E then
begln
6 distance(x)←w(s,x)
7 father(x)←s
end
else
8 distance(x)←∞；
9 whlle X is not empty do
begin
10 choose a vertex u in X for which
distance(u) is minimum；
11 add(father(u),u) to T；
12 X←X─（u）；
13 for cach x in X such that (u,x)∈E do
lf distance(x) ＞distance(u)+w(u,x)then}
begin
15 distancc(x)←distancc(u)w(u,x)；
16 father(x)←u
end
end
while(1)
(
min=MAX_DIST;u=o;
for
(i=o; i
if (adj(i)(i)==o &&
dist(i),length< min
if
(u==o) break;
eise
adj(u)(u)=1;
for
(i=o; i
if
(adj(i)(i)==o && dist(i).length>dist(u).length + adj(u)(i))
(
dist(i).length=dist(u).length+adj(u)(i);
dist(i).pre=u;
)
)
for(i=o;
i
(
if(i!=START_NODE_NUM)
(
if(dist(i).length!=MAX_DIST)
printf(“The shortest distance from
node &d to node &d is &d,with its father as &dn”
START_NODE_NUM,
i, dist(i).length,dist(i).pre);
else
printf(“There is no path from node &d to node &dn”.
START_NODE_NUM,i);
)
)
)
C＞最长路径算法
一、算法
begin
1 for all v in V do length(v) ← 1
2 length(v) ← 0
3 for I ← mun(s) + 1until |V| do
begin
4 let v be vertex such that num(v)=i;
5 for each u uch that(u,v) ∈E do
6 if length(u)≽ 0 and length(v)<
length(u) + w(u,v)
then
begin
7 length(v) ← length(u) + w(u,v)
8 father(u) ← u
end
end
comment at the tertaination of the
proseduce it turns out that for
ach u of length(v)< 0 there is no path from s to v
end
二、最短路径算法的分析与设计：
设从结点S出发，找从它到图中所有其它结点的最短路径，算法的基本思想是：把图中所有结点分成两组，第一组包括已确定最短路径的结点，第二组包括尚未确定最短路径的结点，按最短路径长度递增的顺序逐个把第二组的结点加到第一组中去，直至从S出发可以到达的所有结点都包括到第一组中。在这个过程中，总保持从S到第一组各结点的最短路径长度都不大于从S到第二组的任何结点的最短路径长度。另外，每个结点对应一个距离值，第一组的结点对应的距离值就是从S到此结点的最短路径长度，第二组的结点对应的距离值是从S到些结点的只包括第一组的结点为中间结点的最短路径长度。
具体的做法：一开始第一组只包括结点S，第二组包括其它所有结点。S对应的距离值为0，第二组的结点对应的距离值这样确定：若图中有边，则U的距离值为此边所带的权，否则U的距离值为一个很大的数。然后，每次从第二组的结点中选一个其距离值为最小的结点U加入到第一组中，每往第一组加入一个结点U，就要对第二组的结点的距离值进行一次修正。若加进U做中间结点，使从S到X的最短路径比不加U的为短，则要修改X的距离值。修改后再选距离值最小的结点加入到第一组中。如此进行下去，直到图的所有结点都包括在第一组中，或再也没有可加入到第一组的结点存在。
三、C语言程序shorl.c:
本程序求下图中从S出发到其它各结点的最短路径：（S即为Vo)
#include ＜stdio.h＞
#define
MAX_DIST 1000
#defIne
MAX_NODE_NUM 6
#define
START_NODE_NUM 0
int adj (MAX_NODE_NUM)
(MAX_NODE_NUM)=(0,50,10,MAX_DIST,45,MAX_DIST,
MAX_DIST,0,15,MAX_DIST,5,MAX_DIST,
20,MAX_DIST,0,15,MAX_DIST,MAX_DIST,
MAX_DIST,20,MAX_DIST,0,35,MAX_DIST,
MAX_DIST,MAX_DIST,MAX_DIST,30,0,MAX_DIST,
MAX_DIST,MAX_DIST,MAX_DIST,3,MAX_DIST,0);
(int
length;
int
pre;
) dist(MAX_NODE_NUM);
main(
)
(
int
i,min,u;
for(i=0;i
(
dist(i).length=adj(START_NODE_NUM)(i);
if
(dist(i),length !=MAX_DIST)
dist(i).pre=START_NODE_NUM;
else
dist(i).pre=0;
adj(START_NODE_NUM)(START_NODE_NUM)=1;
四、算法分析与设计
设从结点S出发，找从它到图中所有其它结点的最长路径，算法的基本思想是：先对图中结点进行拓扑排序，为各结点加上唯一的相应顺序号，即如果（U，V）＜E，则NUM（U）＜NUM(V)。接着按下面的做法求出从S出发到其它各结点的最长路径。
算法的具体做法是：先给各结点的LENGTH值赋-1，而S的LENGTH值为0，对S之后的每个结点顺序进行以下操作：如果有结点U，使（U，V）＜E，且LENGT H(u)＞=0,AND
LENGTH(v)＜LENGTH(u)+w(u,v)，则将LENGTH(V)的值修改为LENGTH(W)+W(U,V)，并标记结点V的前一个结点为U，算法结束时如果LENGTH(V)＜0则从S没有路径到V。
五、C语言程序LONG.C:
本程序求下图中从S出发到其它各结点的最长路径：(S即为Vo)
#include
#define
MIN- dist-1
#define
MAX- NODE- NUM 6
#define START- NODE- NUM 0
int adj[MIX- NODE- NUM][MAX- NODE- NUM]=(0,50,10,MIN- dist,45, MIN- dist,
MIN- dist,0,15,
MIN- dist,5, MIN- dist,
20, MIN- dist,0,15,
MIN- dist, MIN- dist,
MIN- dist,20,
MIN- dist,0,35, MIN- dist,
MIN- dist,MIN- dist,MIN- dist,30,0,MIN- dist
MIN- dist,MIN- dist,MIN- dist,3,MIN- dist
struck path
[int]
length;
int
pre;
)
dist [MAX- NODE- NUM];
main(
)
(
int
i.j;
for(i=0
;i< MAX-NODE-NUM ; i++)
dist[i]. length = -1
dist[ START- NODE- NUM ]. Length =0 ;
for(i=
START- NODE- NUM + 1; i< MAX-NODE-NUM;
i++)
(
for(j=0;
j< MAX-NODE-NUM; j++)
if(adj[j][I]!= MIN- dist
&& adj[j][I]!=0 && dist[j]. Length>=0 && dist[i].
Length< dist[j]. Length + adj[j][I])
(
dist[i]. Length= dist[j]. Length
+ adj[j][I]
dist[i]. pre = j
)
)
for(i=0;i<
MAX-NODE-NUM ; i++)
(
if
(i!= START- NODE- NUM )
(
if ( dist[i]. Length! = MIN- DIST
)
prntf( *The longest distance from node %d to node %d,with its fat
her as %dn*
START- NODE- NUM,i,
dist[i]. Length, dist[i].per);
Else printf(*There is no path
from node %d to node ,%dn*
START- NODE- NUM,I);
)
)
)
D＞结论
在示例图1中，该电路共有5个具体电路，其中Vo到V1运算时间假设为：50，V1到V2、V3、V4（各边加权）连算时间分别为15、20、5，余类推，运行本程序，则Vo到V1-V5各电路的最短路径时间则可在程序中获得正确解答。同理，在示例图2中，Vo对V2-V4各电路的最长路径也可在程序编译运行后得出正确的结果。
应用实例：示例图3中共有10个电路，其中第3、6、9电路之间存在反馈，即呈强连结状（Stronglg Comnected），此时就要将其（图中虚线部分）等效成一个电路，其运算时间则要用最短路径算法算之，而对整个电路则要用最长路径算法来算出从第一个电路至某个电路运行所需的时间。这样，用最短路径算法可求出3、6、9电路的计算时间分别为dis[9]=1′、dis[6]=2′、dis[3]=5′、故可将虚线部分等效成一个需时5`的电路，对整体而言，采用最长路算法，可算出第10号电路的最长路径为23′，余类推。
参考文献
1、Dijkstra,E,w.
"A
note on two probleme in connection with graphe"
Numerische
Math.1 PP.269-271.1959
2、白川 功“演习グラフ理论” 日本コロナ社1984
