最短路径规划实验报告.docx

电子科技大学计算机学院
标准实验报告
（实验）课程名称
最短路径规划
电子科技大学教务处制表
告
指导教师：陈昆
;
GrapliKnid kind;
}MGiaph;
〃顶点向量
〃邻接矩阵
〃图的当前顶点数和弧数
〃图的种类标志
：构造一个有向网。
2、Dijkstra算法思想及实现。
一、 算法思想
首先，引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个 终点Vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。 这里强调相对就是说在算法过程中D[i]的值是在不断逼近最终结果但在过程中不一定就 等于最短路径长度。它的初始状态为：若从v到vi有弧，则D[i]为弧上的权值；否则置 D[i]为m显然，长度为D|j]=Miii{D[i]|viev} 的路径就是从v出发的长度最短的 一条最短路径。此路径为(v，Yj)°
那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk,则可 想而知，这条路径或者是(v,vk),或者是(v，xj,vk)。它的长度或者是从v到vk的弧上的权 值，或者是D[j]和从勺到vk的弧上的权值之和。
一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径 (设其终点为X)或者是弧(v,x),或者是中间只经过S中的顶点而最后到达顶点X的路 径。因此，卞一条长度次短的最短路径的长度必是D[j]=Mm{D[i]|vieV-S} 其中，
D[i]或者是弧(¥,vi)上的权值，或者是D[k](vkES)和弧(vk,w)上的权值之和。
二、 算法描述
1)arcs[i,j俵示弧<vi,\j>上的权值。若<vi,yj>不存在，则置arcs[i,j]为co (在本程序 中为MAXCOST)o S为已找到从v出发的最短路径的终点的集合，初始状态为空集。 那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D[i]=arcs[Locate Vex(Gv),i] viGV
)选择 yj,使得 D|j]=Mui{D[i] viGV-S}
)修改从v出发到集合V-S上任一顶点vk町达的最短路径长度。如呆D[j]+arcs|]<D[k] 则修改 D[k]为 D[k]=D[j]+arcs[j,k]o
4)重复2)和3),直到找到目标顶点或遍历所有顶点为止。
六、 实验器材(设备、元器件)：电脑
七、 实验步骤：
程序：
# iiiclude<>
#define m 100
#define TRUE 1
#define FALSE 0 tvpedef stmct Cel{
mt arcs [6] [6]; 〃邻接矩阵
iiit vexiiuni;
};
void main()
{
int d[6].p[6] [6],v,w,final[6],iJ,kjiiin,a[习={ 1,1JJ,1} 各 c,b;
Cel g={ ,mJ,nLnK
& nun,m,.
,5,.
111,11