实验五：分枝限界法_最短路径问题概要.doc

HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 算法设计与分析 实 验 报 告 实验项目 实验五 实验类别 验证性 学生姓名 王龙 学生学号 201400797 完成日期 2016-5-6 指导教师 刘振章 实验成绩 评阅日期 评阅教师 刘振章 实验五：分枝限界法 【】 【】 【】 要求完成：⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。 【 由于要找的是从源到各顶点的最短路径，所以选 Fenzhi函数 在初始化的时候 对最优权重赋上一个最大值 【程序代码】 # include stdio.h # define MAX 9 void input (int d[], int s[], int t[][MAX], int ti[][MAX], int n, int k); void fenzhi (int d[], int s[],int t[][MAX], int ti[][MAX], int n, int k); void output (int d[], int s[], int n); int main () { int n, k; int d[MAX], s[MAX], t[MAX][MAX] = {0}, ti[MAX][MAX] = {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 t[][MAX], int ti[][MAX], int n, int k) { int i, j, m, z; printf (请输入图的边: i, j, t[i][j] \n); for (z=0; zk; z++) { scanf (%d %d %d, i, j, m); t[i][j] = m; ti[i][j] = 1; } for (i = 0; i n; i++) //初始化数组 { d[i] = 99; // 赋个最大值 s[i] = -1; } } void fenzhi (int d[], int s[],int t[][MAX], int ti[][MAX], int n, int k) { int i, j, zi; d[0]=0; s[0]=-1; for (i=0; in; i++) { printf (当前扩展节点：%d，权重：%d : \n, i, d[i]); for (j=0; jn; j++) { if (ti[i][j] == 1 ) { if ( d[j]t[i][j]+d[i]) { d[j]=t[i][j]+d[i]; //最短长度 s[j]=i; //前驱结点 } if (j != n /* j != 6 */ ) printf (入队结点：%d ,最优权重：%d \n, j, d[j]); } } printf (\n); } } void output (int d[], int s[], int n) { int i, j=0, zi[MAX]; printf (从源点到各个结点的最短路径: \n); for (i=0; in; i++) printf (dist[%d] = %d \n, i, d[i]); printf (\n); printf (从源点到终点的最短路径长度为: %d \n, d[n-1]); printf (其路径为: %d , n-1); zi[j] = s[n-1]; printf (---- %d , zi[j]); while (zi[j] != 0) { j++; zi[j] = s[zi[j-1]]; printf (---- %d , zi[j]); } printf (\n); } 【运行结果】 图1 输入数据