1. 首页首页
  2. 编程汇总编程汇总

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

编程汇总 • • 阅读 2

深度搜索算法查找最短路径的方法_深度优先搜索算法如图 百度地图上有 5 个地点 各个地点间是单向的路径 试求出从 1 到 5 的最短路径 从图中可以得到一个 5 5 的二维矩阵 利用深度搜索算法 求出最短路径 从最后的运行结果 可以直观的看出搜索的过程 代码实现如下 include pch h include include include using namespace std define M

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

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

代码实现如下：

#include "pch.h"

#include 

#include 

#include 

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 vecPath;

void ShowPath()

{
for (size_t i=0; 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{
	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;

}

运行结果：打印出路径

编程小号
上一篇 2025-01-16 19:33
下一篇 2025-01-16 19:27

相关推荐

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/hz/148872.html