深度搜索算法查找最短路径的方法_深度优先搜索算法

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;

#define M 99999999

const int CityNum = 5;
const int cityMap[CityNum][CityNum] =
{
	0,2,M,M,10,
	M,0,3,M,7,
	4,M,0,4,M,
	M,M,M,0,5,
	M,M,3,M,0
};
bool book[CityNum] = { false };
int iMin = M;
vector<int> vecPath;
void ShowPath()
{
	for (size_t i=0; i<vecPath.size(); i++)
	{
		printf("->%d", vecPath[i]+1);
	}
}
void dfs(int iCur, int iDes, int iDis)
{
	vecPath.push_back(iCur);
	if (iDis > iMin)
	{
		ShowPath();
		printf("->More than Min:%d>%d\r\n", iDis, iMin);
		return;
	}
	if (iDes == iCur)
	{
		if (iDis < iMin)
		{
			iMin = iDis;
		}
		ShowPath();
		printf("->MinPath:%d\r\n", iMin);
		return;
	}

	for (int i=0; i<CityNum; i++)
	{
		if (cityMap[iCur][i] != M && !book[i])
		{
			book[i] = true;
			dfs(i, iDes, iDis + cityMap[iCur][i]);
			vecPath.pop_back();
			book[i] = false;
		}
		else
		{
			ShowPath();
			printf("->%dX\r\n", i + 1);
		}

	}

}

int main()
{
	book[0] = true;
	dfs(0, 4, 0);
	printf("Shortest path is %d", iMin);
	
	return 0;
}