寻找无向图的最短路径（有跳数限制）

需要寻找一条有效的最短路径。给定一个无向网络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;
}