一、课设背景：单源最短路径问题

 

单源最短路径是图论经典问题：给定带权有向图 G=(V,E) 和一个“源顶点”，求源点到图中所有其他顶点的最短路径长度（路径长度为路径上各边权值之和）。

 

本次课设要求“随机生成图+随机选源点+求解最短路径”，我选择用回溯法实现（注：回溯法并非该问题的最优解法，但能直观体现“枚举所有路径”的思路，适合理解问题本质）。

 

二、回溯法核心思路

 

回溯法通过枚举所有可能的路径，记录源点到每个顶点的最小路径长度，核心逻辑：

 

1. 从源点出发，递归遍历所有可达顶点；

 

2. 每到达一个顶点，计算当前路径的权值和；

 

3. 若当前权值和小于该顶点已记录的最短路径长度，则更新最短路径；

 

4. 遇到“已访问顶点（避免环）”时，剪枝并回溯。

 

三、课设实现（C++）

 

步骤1：随机生成带权有向图（邻接矩阵存储）

 

生成指定顶点数的随机图，边权取1~10的整数，无直接边则用INT_MAX表示。

#include <iostream>

#include <vector>

#include <random>

#include <climits>

#include <algorithm>

using namespace std;

 

// 生成n个顶点的随机带权有向图（邻接矩阵）

vector<vector<int>> generateRandomGraph(int n) {

    vector<vector<int>> graph(n, vector<int>(n, INT_MAX));

    random_device rd;

    mt19937 gen(rd());

    uniform_int_distribution<> weightDist(1, 10); // 边权范围：1~10

    uniform_int_distribution<> adjDist(1, n-1); // 每个顶点的邻接顶点数：1~n-1

 

    for (int i = 0; i < n; ++i) {

        // 随机选择邻接顶点（排除自身）

        vector<int> candidates;

        for (int j = 0; j < n; ++j) if (j != i) candidates.push_back(j);

        shuffle(candidates.begin(), candidates.end(), gen);

        

        // 随机选1~n-1个邻接顶点并赋值边权

        int adjNum = adjDist(gen);

        for (int k = 0; k < adjNum; ++k) {

            int j = candidates[k];

            graph[i][j] = weightDist(gen);

        }

    }

    return graph;

}

步骤2：回溯法求解单源最短路径

 

通过递归回溯枚举所有路径，维护shortest数组记录最短路径长度，visited数组标记当前路径的已访问顶点（避免环）。

// 回溯法核心递归函数

void backtrack(const vector<vector<int>>& graph, int currentVertex, int currentLen, 

               vector<int>& shortest, vector<bool>& visited) {

    int n = graph.size();

    // 遍历当前顶点的所有邻接顶点

    for (int nextVertex = 0; nextVertex < n; ++nextVertex) {

        // 条件：有边 + 未被当前路径访问

        if (graph[currentVertex][nextVertex] != INT_MAX && !visited[nextVertex]) {

            int newLen = currentLen + graph[currentVertex][nextVertex];

            // 更新到nextVertex的最短路径

            if (newLen < shortest[nextVertex]) {

                shortest[nextVertex] = newLen;

            }

            // 递归探索下一个顶点

            visited[nextVertex] = true;

            backtrack(graph, nextVertex, newLen, shortest, visited);

            visited[nextVertex] = false; // 回溯：撤销访问标记

        }

    }

}

 

// 回溯法入口函数（初始化+调用递归）

vector<int> backtrackShortest(const vector<vector<int>>& graph, int start) {

    int n = graph.size();

    vector<int> shortest(n, INT_MAX); // 初始化为无穷大

    vector<bool> visited(n, false); // 访问标记数组

    shortest[start] = 0; // 源点到自身的距离为0

    visited[start] = true; // 标记源点已访问

    backtrack(graph, start, 0, shortest, visited);

    return shortest;

}

四、课设总结

 

1. 回溯法的优缺点

 

• 优点：思路直观，能枚举所有可能路径，确保找到最短路径；

 

• 缺点：时间复杂度为指数级 O(n!) ，仅适用于顶点数≤10的小规模图（顶点数增多时效率极低）。

 

（实际工程中，单源最短路径更常用Dijkstra算法（非负权）或Bellman-Ford算法（支持负权））

 

2. 课设收获

 

通过C++实现回溯法，深入理解了“回溯+剪枝”的核心思想，同时明确了不同算法在图问题中的适用场景——后续可补充更高效的算法做对比。