摘 要：确定两点之间最短路径，通常要求该路径满足两点之间的权之和最小。为此采用层次遍历图的思想，设计了一种新的结构存放路径选择信息，找到一种确定这种最短路径的算法，并给出了算法描述以及实例。
关键词：邻接表；边链表；层次遍历图;队列；最短路径

在实际生活中常常会遇到求最短路径问题，如：从Ａ地到Ｂ地有若干条路可选，每条边上都标有象征某种意义的权值。有人选择路径的方法是希望总路径的权之和最小；有人选择中转次数最少；而还有人希望在中转次数最少的条件下尽量权之和最小。确定权之和最小的最短路径算法目前国内外公认较好的是Dijkstra算法和Floyed算法，这两种算法已被广泛用于生活中各个领域，如：网络寻优、道路交通等。但这些算法都只单纯地考虑路径中权之和达到最小,而并未考虑路径中边数能否也最少。而在目前高科技迅猛发展的经济时代，人们在选择出行方案时可能会更加注重降低因中转而产生的精力和时间的消耗而不会过多在意为此多出的花费。因此，许多情况下出行的人们会考虑中转次数尽量少，然后在相同的中转次数下优先选择花钱最少的路径作为选择方案。
本文提出了一种确定两个顶点之间经过的边数最少且相同边数前提下权值之和最小的最短路径的一种算法。在本算法中，采用邻接表存储结构存储原始图，在层次遍历法的思想遍历图的基础上进行了修改，设计了一种新的结点结构存放路径选择中的信息。当遍历到终点结点出现时，终止遍历过程，然后在目标结构中从该终点开始按指定的指针域层层向上搜索并输出经过的每一个结点序号直到指针为空为止。输出的序列就是要找的最短路径。
1 数据结构的设计及算法
设有n个顶点的一个无向图，图中每条边都标有代表某种意义的权值，现求从顶点i到顶点j的边数最少且权值也最小的最短路径。
1.１ 数据结构的设计
(1) 采用邻接表作为原图的存储结构
其中的表头结点vnode中存放顶点信息如：城市名称(cityname)，对应顶点的序号(verindex)以及指向该顶点的边链表的头指针域（firstarc），如图1所示。边链表结点node中存放顶点的序号(verindex)、表头结点到该顶点的边上的权值(weight)以及指向与表头顶点邻接的下一个顶点的指针域（nextarc），如图2所示。

C语言描述如下：
typedef struct node
{ int adjindex ;
int weight ;
struct node *nextarc ;
} Node ;
typedef struct vnode
{char cityname[20];
int verindex;
struct node *firstarc;
}Vnode ;
　 n个顶点图的邻接表就定义为：vnode g[n+1];其中下标为０的元素不用。
(２) 存放路径信息的结点结构BT
该结构中的顶点有4个域,如图3所示。

C语言描述为：
typedef struct bt
{struct bt *parent ,*brother ,*first ;
int data ;
}BT ;
其中：
*parent：记录该结点被确定之前的最短路径上的前一个结点，称之为该结点的双亲。
*brother：记录该结点所在的边链表中下一个未被访问过的顶点。
*first：记录该结点的边链表中第一个未被访问的顶点序号。
data：记录该结点序号。
(３)建立一个ＢＴ类的长度为n+1队列q并初始化为空队。
(４) 建立一个整型一维数组visited[n+1]，用来存放每个顶点是否已被访问过的标志，未被访问其对应元素值为０，否则为１，因此初始化该数组全部为０。
1.２ 算法
以交通问题为例，确定从城市Ａ（对应序号为i）到城市Ｂ（对应号为j）经过的边数最少且相同边数条件下权之和也最小的最短路径。
算法描述中用到的变量声明约定如下：
Node *p,*q;
BT *t ,*r ,*u ,*q[n+1] ;
Vnode g[n+1] ;
int visited[n+1]={0}, i, j, w, k;
(1) 建立邻接表，为了确保找到的边数最少的路径也一定是相同边数下权值之和最小的一条，故要求每个顶点的边链表中的权值(weight)都是按从小到大的顺序连接起来的。为此，在算法中先将输入的所有边按权值进行降序排列，然后在建立图的邻接表时，依次考查每一条边，将该边的起点和终点分别以头插法插入到相应终点和起点的边链表中。
(2) 从顶点i开始，申请一个ＢＴ类的结点t，其中t->parent＝NULL，t->brother=NULL，t->first=NULL，t->data=i，visited[i]=1，r=t，并且将t结点加入q队列。
(3)若q队列未空，将队首元素出队,即u=q[++front]，并获取u->data在邻接表中的边链表的头指针，即p=g[u->data]->firstarc，设置一个标志变量k=1（当k为１时，说明刚出队的队首结点u的边链表中还没有一个未被访问的结点加入到目标路径中）。
一个结点刚出队时，该结点的边链表中肯定还没有一个结点被加入到目标路径中，因此该结点将作为它的边链表中的结点的双亲结点。
(4) 若p非空（即双亲结点边链表还未访问完），则获取w=p->adindex，并按序执行进行如下三种情况：
①若p指向的结点未被访问过，即：visited[w]=0，且k=1，则说明结点w是双亲结点的边链表中第一个未被访问过的结点，故w应该加入目标结构中成为双亲u的first。因此为 w申请一个ＢＴ类的结点空间t，此时，t为u的first，t的parent为u，即：u->first=t，t->parent=u，t->data=w，t->brother=NULL，t->first=NULL，r=t，并将t入q 队列。
②若p指向的结点未被访问过，且k=0， 则说明w不是双亲结点的边链表中第一个未被访问过的结点，故w应作为前一个未被访问结点t的brother而加入到目标结构中。因此申请一个BT类结点空间t，t只能作为r的兄弟连接，t的双亲仍为u,即：r->brother=t，t->parent=u，t->first=NULL，t->brother=NULL，t->data=w，r=t。
③若p指向的结点w未被访问过，则置visited[w]为1且k为0。此时再做如下判断：
若t->data＝＝j，说明了刚加入目标结构中的结点就是终点，最短路径已经找到。因此从t开始按双亲域层层向上搜索目标结构并一一输出每个结点的data域，直到结点为空为止，输出的就是要找的路径，结束本算法。
若t->data!=j说明刚加入目标结构的结点还不是终点，则继续考虑边链表的下一个结点，即p=p->nextarc，转④继续。
④若p指向的结点w已被访问过,则p=p->nextarc，转4）继续。
(5) 若p为空，说明双亲u的边链表已全部经遍历，应该从队列出取出一个新的结点继续考查。故转③继续。 (6) 若q已空，则说明从i到j无路径，算法结束。
2 实例
以下以一个交通图为例,求任意两点之间的边数最少且权之和也最小的最短路径。如图4所示。
在该图中各顶点分别代表不同的城市名，两点之间有边相连代表两个顶点邻接，边上的权值代表两点之间乘车的费用。
问题:寻找从1~５的边数最少且权之和最小的路径。
图4所建的邻接表如图5所示。

按照上述算法所得的目标结构图如图6所示。

从终点5开始按praent域层层向上搜索直到结点为
空为止，得一结点序列5，4，2，1，因此，1->2->4->5就是该问题要找的从结点1到结点5的最短路径，其权之和6也是相同边数的路径中权之和最小的一个。
本文采用了图的邻接表结构以及层次遍历思想，给出了一种确定任意两点之间中转边数最少且权值最小的最短路径的算法，并给出了一个实例。这种算法并不是最理想的，但至少是一种有效的实现方法，还有待于进一步优化和改进。
参考文献
[１] 张群哲．数据结构（C语言版）[M].西安:西安电子科技出版社，2008：131-140.
[２] 安训国,刘俞．数据结构（第三版）.[M]大连:大连理工大学出版社，2003：136-160.