//?Assignment_2_SY1606207.cpp?:?Defines?the?entry?point?for?the?console?application.
/*
?*?主要思路：?
?*?????遍歷：利用棧結(jié)構(gòu)，通過深度優(yōu)先搜索遍歷路徑
?*?????定界：每一個(gè)最短路徑值更小的可行解確定了新的下界
?*?????剪枝：先利用Dijkstra算法計(jì)算每個(gè)城市到目的城市的最短路徑和最小花費(fèi)，當(dāng)算法運(yùn)行到某個(gè)城市后，
?*??????????計(jì)算在棧里的城市的路徑長(zhǎng)度?+?這個(gè)城市到目的城市的最短路徑，以及在棧里的城市的路徑花費(fèi)?+?這個(gè)城市到目的地的最小花費(fèi)，
?*??????????與當(dāng)前最優(yōu)的可行解以及約束條件進(jìn)行比較，從而達(dá)到剪枝的目的
?*/

#include?“stdafx.h“

#include?
#include?
#include?
#include?

using?namespace?std;

#define?MAX_NODE?60?//?最大節(jié)點(diǎn)數(shù)
#define?MAX_INT?9999?//?定義最大整數(shù)
#define?MAX_COST?1500?//?定義最大花費(fèi)

int?n1?n2;?//?分別表示矩陣的行和列
deque?queueMinPath;?//?記錄已得到的最短路徑
int?minPath;?//?記錄最短路徑長(zhǎng)度
int?costOfMinPath;?//?記錄最短路徑的花費(fèi)

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

	clock_t?startTime?endTime;
	startTime?=?clock（）;

	cout?<
	int**?readTxtToArrayWithoutKnowRowOrColumn（const?char*?strPath）;?//?把txt文件讀進(jìn)二維數(shù)組
	void?findPathWithDFS（int?**m1?int?**m2?int?fn?int?tn）;?//?深度優(yōu)先

	int?pI

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件???????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