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

1、HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY算法设计与分析实 验 报 告实验项目实验五实验类别验证性学生姓名王龙学生学号201400797完成日期2016-5-6指导教师刘振章实验成绩评阅日期评阅教师刘振章实验五：分枝限界法【实验目的】应用分枝限界法的算法设计思想求解单源最短路径问题。【实验性质】验证性实验。【实验内容与要求】采用分支限界法编程求源点0到终点6的最短路径及其路径长度。要求完成：算法描述写出程序代码完成调试进行过程与结果分析。【算法思想及处理过程】由于要找的是从源到各顶点的最短路径，所以选用一个数组存起来.Fenzhi函数: 由于先前赋值时,

2、 用一个二维数组将结点的有向图标记存起来了( 有边为1, 无边为0 ),并且又用另外一个二维数组将其权重存起来了; 首先, 通过双重for循环, 通过if语句判断, 如果标记为1, 并且相加的权重小于先前最优权重( 在初始化的时候, 对最优权重赋上一个最大值 ), 则求得最优权重, 并且用一维数组将权重存起来, 而且用一维数组将前驱结点存起来.你然后, 一直循环下去, 直到循环到目的结点.【程序代码】# include <stdio.h># define MAX 9void input (int d, int s, int tMAX, int tiMAX, int n, int k

3、);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);inp

4、ut (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 ("请输入图的边: < i, j, tij > n"); for (z=0; z<k; z+) scanf ("%d %d %d", &i, &j, &m); tij = m; tiij = 1; fo

5、r (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; i<n; i+)printf ("当前扩展节点：%d，权重：%d : n", i, di);for (j=0; j<n; j+)if (tiij = 1 )if ( dj>tij+di)dj=tij+di; /最短长度sj=i;/前驱结点if (j !=

6、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<n; i+)printf ("dist%d = %d n", i, di);printf ("n");printf ("从源点到终点的最短路径长度为: %d n", dn-1);printf ("其路径为: %d ", n-1);zij = sn-1;printf ("-> %d ", zij);while (zij != 0)j+;zij = szij-1;printf ("-> %d ", zij);printf ("n");【