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