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

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

如图，百度地图上有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;
		}
		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;
}

Jetbrains全家桶1年46，售后保障稳定

运行结果：打印出路径