大家好，又见面了，我是你们的朋友全栈君。

如图，百度地图上有5个地点，各个地点间是单向的路径，试求出从1到5的最短路径。

从图中可以得到一个5*5的二维矩阵，利用深度 搜索 算法，求出最短路径。从最后的运行结果，可以直观的看出搜索的过程

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

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

代码实现如下：

#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;
			ShowPath();
			printf("->%dX\r\n", i + 1);
int main()