需要寻找一条有效的最短路径。给定一个无向网络G=(V,A,C)，其中V是节点集合，A是无向边集合，C是边路径长度集合，对于每条边a(i,j)，对应有c(i,j)>=0。当给定两节点（源点和汇点）以及跳数pathLength，求解两点之间的最短距离，要求其跳数满足大于pathLength。
要求：设计算法，分析其时间复杂度。请提供源程序。输入的测试数据如下所示：
7 12 2
0 1 2 3 4 5 6
0 4 74
1 4 60
2 4 60
3 4 97
5 0 100
5 1 100
5 2 100
5 3 100
6 0 100
6 1 100
6 2 100
6 3 100
数据说明如下：
第1行：7表示7个节点；12表示12条链路；2表示跳数pathLength。
第2行：0 1 2 3 4 56：表示有7个节点，节点标识为0,1,…,6。
第3-14行：表示边，如0 4 74表示节点0到节点4的边距离为74。
#include <iostream>
#include <unordered_map>
#define INF 2147483647
using namespace std;
unordered_map<int,int>nameToIndex;
unordered_map<int,int>indexToName;
int vexNum;
int edgeNum;
int pathLendth;
int vS;
int vD;//源点，目标点
int res[120];//保存被访问的路径节点
int minL = INF;//最短路径
int num;
int path[120];//前驱
int g[120][120];//领接矩阵存储边
int isVisited[120];//节点访问情况
void Dfs(int index,int sum) { //index为已访问的点个数，sum为总长
if(sum>=minL) {
return;//没找到更小的路径，直接退出
} else if(path[index-1]==vD) { //找到了目标点
if(index-1>pathLendth && sum<minL) { //满足跳数和最小
for(int i = 0; i<index; i++) {
res[i] = path[i];//将path数组复制
}
minL = sum;
num = index;
}
return;//结束
} else {
for(int i = 0; i<vexNum; i++) { //遍历点
if(!isVisited[i] && g[path[index-1]][i]<INF) { //没被访问且有边
path[index] = i;//将点i存储在path数组
isVisited[i] = 1;//i被访问
Dfs(index+1,sum+g[path[index-1]][i]);//递归访问下一个
isVisited[i] = 0;//回溯
}
}
}
}
int main() {
printf("请输入点数，边数，跳转数\n");
scanf("%d %d %d",&vexNum,&edgeNum,&pathLendth);
for(int i = 0; i<vexNum; i++) { //初试化边
for(int j = 0; j<vexNum; j++) {
g[i][j] = INF;
}
}
printf("输入节点标识\n");
int tmpName;
int tmpIndex = 0;
for(int i = 0; i<vexNum; i++) {
scanf("%d",&tmpName);//读取点的值
nameToIndex[tmpName] = tmpIndex;//记录值与数组下标的对应关系
indexToName[tmpIndex] = tmpName;
tmpIndex++;
}
int tmpV1;
int tmpV2;
int tmpL;
printf("请输入点A，点B，边长\n");
for(int i = 0; i<edgeNum; i++) {
scanf("%d %d %d",&tmpV1,&tmpV2,&tmpL);
tmpV1 = nameToIndex[tmpV1];
tmpV2 = nameToIndex[tmpV2];
g[tmpV1][tmpV2] = tmpL;//邻接矩阵存储边
g[tmpV2][tmpV1] = tmpL;
}
for(int i = 0; i<vexNum; i++) {
isVisited[i] = 0;//访问情况初始化
}
printf("源点，目标点\n");
scanf("%d %d",&vS,&vD);
vS = nameToIndex[vS];//获取源点下标
vD = nameToIndex[vD];//目标点下标
isVisited[vS] = 1;
path[0] = vS;//初始化
Dfs(1,0);
if(minL<INF) {
printf("%d\n",minL);
printf("路径为:");
for(int i = 0; i<num; i++) {
printf("%d ",res[i]);
}
} else {
printf("不存在\n");
}
return 0;
}