实验五：分枝限界法-最短路径问题

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY算法设计与分析实 验 报 告实验项目实验五实验类别验证性学生姓名王龙学生学号完成日期2016-5-6指导教师刘振章实验成绩评阅日期评阅教师刘振章实验五：分枝限界法【实验目的】应用分枝限界法的算法设计思想求解单源最短路径问题。【实验性质】验证性实验。【实验内容与要求】采用分支限界法编程求源点0到终点6的最短路径及其路径长度。要求完成：算法描述写出程序代码完成调试进行过程与结果分析。【算法思想及处理过程】由于要找的是从源到各顶点的最短路径，所以选用一个数组存起来.Fenzhi函数: 由于先前赋值时, 用一个二维数组将结点的有向图标记存起来了( 有边为1, 无边为0 ),并且又用另外一个二维数组将其权重存起来了; 首先, 通过双重for循环, 通过if语句判断, 如果标记为1, 并且相加的权重小于先前最优权重( 在初始化的时候, 对最优权重赋上一个最大值 ), 则求得最优权重, 并且用一维数组将权重存起来, 而且用一维数组将前驱结点存起来.你然后, 一直循环下去, 直到循环到目的结点.【程序代码】# include # define MAX 9void input (int d, int s, int tMAX, int tiMAX, int n, int k);void fenzhi (int d, int s,int tMAX, int tiMAX, int n, int k);void output (int d, int s, int n);int main ()int n, k;int dMAX, sMAX, tMAXMAX = 0, tiMAXMAX = 0;n = 7; k = 11;printf (请输入结点的个数:);scanf (%d, &n);printf (请输入结点的边数:);scanf (%d, &k);input (d, s, t, ti, n, k);fenzhi (d, s, t, ti, n, k);output (d, s, n);return 0;void input (int d, int s, int tMAX, int tiMAX, int n, int k)int i, j, m, z;printf (请输入图的边: n); for (z=0; zk; z+) scanf (%d %d %d, &i, &j, &m); tij = m; tiij = 1; for (i = 0; i n; i+) /初始化数组 di = 99; / 赋个最大值 si = -1; void fenzhi (int d, int s,int tMAX, int tiMAX, int n, int k)int i, j, zi;d0=0; s0=-1; for (i=0; in; i+)printf (当前扩展节点：%d，权重：%d : n, i, di);for (j=0; jtij+di)dj=tij+di; /最短长度sj=i;/前驱结点if (j != n /* & j != 6 */ ) printf (入队结点：%d ,最优权重：%d n, j, dj); printf (n);void output (int d, int s, int n)int i, j=0, ziMAX;printf (从源点到各个结点的最短路径: n);for (i=0; i %d , zij);while (zij != 0)j+;zij = szij-1;printf (- %d , zij);printf (n);【运行结果】图1 输入数据图2 输出扩展结点图3