bound_branch.c

分支界限法的C语言源码 实现了计算两个城市之间一定开销的基础上的最短路径

/*
 *
 * 分支定界算法
 * SY0806503 张良
 * 
 * 在Microsoft Windows XP Professional SP3下调试通过
 * 
 * 运行时如果指定参数 "--all" 则可以按顺序输出所有找到的解 最后一个输出的是最优解
 * 如果不指定参数 则输出最优解
 * 如果指定错误参数 程序拒绝执行
 * 
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <climits>

#define MAX 50
#define INFINIT 9999
// 道不通

typedef struct road {
	int total_dist;
	// 总路程
	int total_cost;
	// 总费用
	int total_path[MAX];
	// 路径信息
	int path_length;
	// 路径长度
} ROAD;

ROAD path[MAX];
int road_counter;
// 记录所有找到的路径

int dist[MAX][MAX];
int cost[MAX][MAX];
// 原始数据矩阵

int mini_dist[MAX][MAX];
int mini_cost[MAX][MAX];
// 最小化矩阵

int stack[MAX];
int top = 0;
int stack_index;
// 用于深度优先搜索的堆栈

int selected_city[MAX];
// 用于测试是否产生回路的辅助信息

int current_dist = 0;
// 当前距离值

int current_cost = 0;
// 当前开销值

int dist_bound = INT_MAX;
// 初始最短距离上界
// 设为最大整数

int cost_bound = 1200;
// 最小开销上界

void read_data(void);
// 从文件读入数据

void flyod_warshell(void);
// 弗洛伊德算法

void output(int, char**);
// 输出结果

main(int argc, char **argv) {
	int current, next, last_next;
	int index;
	
	read_data();

	flyod_warshell();
	
	// 初始化堆栈
	stack[top++] = 0;
	// 当前城市
	last_next = 1;
	// 下一个城市
	
	selected_city[0] = 1;
	// top++;
	
	while (top) {
		current = stack[top - 1];
		next = last_next;

		for (index = next + 1; index < MAX; index++) {
			if (dist[current][index] == INFINIT ||
				selected_city[index] ||
				current_dist + mini_dist[current][MAX - 1] > dist_bound ||
				current_cost + mini_cost[current][MAX - 1] > cost_bound) {
				continue;
				// 道不通 || 形成回路 || 超过界限
			} else {
				break;
				// 找到合适的城市
			}
		}

		if (index == MAX) {
			// 找不到目的地

			top--;
			current_dist -= dist[stack[top - 1]][stack[top]];
			current_cost -= cost[stack[top - 1]][stack[top]];
			selected_city[stack[top]] = 0;
			last_next = stack[top];
			// 回溯一步
			// 将最后一个加入的城市信息删除 从下一个开始继续搜索
			//top--;
		} else {
			// 找到一个合理的中间城市

			current_dist += dist[stack[top - 1]][index];
			current_cost += cost[stack[top - 1]][index];
			stack[top++] = index;
			selected_city[index] = 1;
			last_next = 1;
			// 记住当前状态
			// 将这个城市的信息加入 准备下一次搜素
			
			if (index == MAX - 1) {
				// 找到目的地

				path[road_counter].total_dist = current_dist;
				path[road_counter].total_cost = current_cost;
				// 记住最后一个城市的信息

				for (stack_index = 0; stack_index < top; stack_index++) {
					path[road_counter].total_path[stack_index] = stack[stack_index];
				}
				path[road_counter].path_length = stack_index;
				road_counter++;
				// 记住整条路径

				dist_bound = current_dist;
				// 更新路径长度上界
				
				top--;
				current_dist -= dist[stack[top - 1]][stack[top]];
				current_cost -= cost[stack[top - 1]][stack[top]];
				selected_city[stack[top]] = 0;
				
				top--;
				current_dist -= dist[stack[top - 1]][stack[top]];
				current_cost -= cost[stack[top - 1]][stack[top]];
				selected_city[stack[top]] = 0;
				
				last_next = stack[top];
				// 开始下一次搜索
			}
		}
	}
	//printf("[%d]\n", road_counter);
	output(argc, argv);
	// 按照参数要求输出结果
}

void read_data() {
	FILE *f_dist, *f_cost;
	int i, j;
	
	f_dist = fopen("m1.txt", "r");
	f_cost = fopen("m2.txt", "r");
	
	if (f_dist == NULL || f_cost == NULL) {
		fprintf(stderr, "%s\n", "open file failed!");
		exit(-1);
	}
	
	for (i = 0; i < MAX; i++) {
		for (j = 0; j < MAX; j++) {
			fscanf(f_dist, "%d", &dist[i][j]);
			fscanf(f_cost, "%d", &cost[i][j]);
		}
	}
	
	fclose(f_dist);
	fclose(f_cost);
}

void flyod_warshell() {
	int i, j, k;
	
	for (i = 0; i < MAX; i++) {
		for (j = 0; j < MAX; j++) {
			mini_dist[i][j] = dist[i][j];
			mini_cost[i][j] = cost[i][j];
		}
	}
	
	for (k = 0; k < MAX; k++) {
		for (i = 0; i < MAX; i++) {
			for (j = 0; j < MAX; j++) {
				if (mini_dist[i][j] > mini_dist[i][k] + mini_dist[k][j]) {
					mini_dist[i][j] = mini_dist[i][k] + mini_dist[k][j];
				}
				if (mini_cost[i][j] > mini_cost[i][k] + mini_cost[k][j]) {
					mini_cost[i][j] = mini_cost[i][k] + mini_cost[k][j];
				}
			}
		}
	}
	
}

void output(int type, char **para) {
	// 不同的输出方式
	int i, j;
	if (type == 1) {
		// 如果不指定命令行参数 默认输出最优解
		fprintf(stdout, "%s\n", "Best way along city 1 to city 50 with shortest path and cost below 1200:");
		fprintf(stdout, "Distance:%4d, Cost:%4d\n", path[road_counter - 1].total_dist, path[road_counter - 1].total_cost);
		fprintf(stdout, "Path:");
		for (i = 0; i < path[road_counter - 1].path_length - 1; i++) {
			fprintf(stdout, "[%d]->", path[road_counter - 1].total_path[i] + 1);
		}
		fprintf(stdout, "[%d]\n", path[road_counter - 1].total_path[i] + 1);
	} else if (!strcmp(para[1], "--all")) {
		// 如果制定参数 "all" 输出所有找到的解 最后一个为最优解
		for (i = 0; i < road_counter; i++) {
			fprintf(stdout, "Way %02d:\n", i + 1);
			fprintf(stdout, "\tDistance:%4d, Cost: %4d\n", path[i].total_dist, path[i].total_cost);
			fprintf(stdout, "\tPath:");
			for (j = 0; j < path[i].path_length - 1; j++) {
				fprintf(stdout, "[%d]->", path[i].total_path[j] + 1);
			}
			fprintf(stdout, "[%d]\n", path[i].total_path[j] + 1);
		}
		fprintf(stdout, "Way %02d is the best one along city 1 to city 50 with shortest path and cost below 1200\n", i);
	} else {
		// 其他情况 打印使用方法
		fprintf(stderr, "%s\n", "Usage: bound_branch [--all]");
	}

}