大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}运行结果：打印出路径
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/234337.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...