分支定界算法求解带约束的最短路径问题

分支定界求解带约束条件的最短路径问题，包含源代码和可执行文件

// Assignment_2_SY1606207.cpp : Defines the entry point for the console application.
/*
 * 主要思路： 
 *     遍历：利用栈结构，通过深度优先搜索遍历路径
 *     定界：每一个最短路径值更小的可行解确定了新的下界
 *     剪枝：先利用Dijkstra算法计算每个城市到目的城市的最短路径和最小花费，当算法运行到某个城市后，
 *          计算在栈里的城市的路径长度 + 这个城市到目的城市的最短路径，以及在栈里的城市的路径花费 + 这个城市到目的地的最小花费，
 *          与当前最优的可行解以及约束条件进行比较，从而达到剪枝的目的
 */

#include “stdafx.h“

#include 
#include 
#include 
#include 

using namespace std;

#define MAX_NODE 60 // 最大节点数
#define MAX_INT 9999 // 定义最大整数
#define MAX_COST 1500 // 定义最大花费

int n1 n2; // 分别表示矩阵的行和列
deque queueMinPath; // 记录已得到的最短路径
int minPath; // 记录最短路径长度
int costOfMinPath; // 记录最短路径的花费

int main（int argc char* argv[]） {

	clock_t startTime endTime;
	startTime = clock（）;

	cout << endl << “程序开始运行“ << endl << endl;	

	int** readTxtToArrayWithoutKnowRowOrColumn（const char* strPath）; // 把txt文件读进二维数组
	void findPathWithDFS（int **m1 int **m2 int fn int tn）; // 深度优先

	int pI

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       7095  2016-12-21 16:57  分支定界算法求解带约束的最短路径问题\Assignment_2.cpp

     文件     156160  2016-12-21 16:46  分支定界算法求解带约束的最短路径问题\Assignment_2.exe

     文件      12010  2016-12-20 21:56  分支定界算法求解带约束的最短路径问题\m1.txt

     文件       8861  2016-12-20 21:56  分支定界算法求解带约束的最短路径问题\m2.txt

     目录          0  2016-12-21 16:57  分支定界算法求解带约束的最短路径问题

----------- ---------  ---------- -----  ----

               184126                    5