有向有环图两点间最长路径C++实现问题排查

你之前使用的拓扑排序+动态规划的最长路径方案，天生不支持有环有向图，失效是必然结果：

• 基于拓扑排序的最长路径DP算法仅适用于有向无环图（DAG）：算法的核心前提是图中不存在环，可以通过拓扑序保证处理某个节点时，所有能到达它的前驱节点的最长距离已经计算完成。
• 有环存在时，Kahn拓扑排序会直接把环上所有节点排除在序列外，这些节点的距离值要么是初始化的无效值，要么是迭代过程中的中间错误值，最终计算出的最远节点结果完全不可信。
• 另外要明确：任意图的最长简单路径问题属于NP-hard问题，不存在多项式时间通用解法，但你场景固定为8×8共64个节点，完全可以通过剪枝搜索快速得到结果。

方案选型 #

节点总数刚好为64，选择带访问状态位掩码的深度优先搜索+多层剪枝实现即可：用64位无符号整数uint64_t存储访问状态，每个bit对应一个坐标节点是否在当前路径中，不需要额外visited数组，内存开销极低。
核心剪枝逻辑：

• 剪枝1：当前路径长度 + 剩余未访问节点数 ≤ 已经找到的到{7,7}的最长路径长度时，直接回溯，不需要继续搜索。
• 剪枝2：每次搜索优先走距离终点{7,7}曼哈顿距离更远的邻接节点，更快找到长路径，提前抬高剪枝阈值，大幅减少无效搜索分支。
• 剪枝3：如果当前路径已经覆盖全部64个节点且当前位置是{7,7}，直接终止所有搜索，这就是理论最长路径。

核心实现代码 #

#include <bits/stdc++.h>
using namespace std;

// 坐标(x,y)转节点索引 范围0~63
inline int get_idx(int x, int y) { return x * 8 + y; }
// 节点索引转坐标
inline pair<int, int> get_pos(int idx) { return {idx / 8, idx % 8}; }

vector<int> adj[64]; // 邻接表，存储邻接节点的索引值
int max_len = -1;
vector<int> best_path; // 存储最终最长路径的节点索引序列
const int END_NODE = get_idx(7, 7);

// 计算两点曼哈顿距离，用于搜索顺序排序
inline int manhattan(int idx1, int idx2) {
    auto [x1, y1] = get_pos(idx1);
    auto [x2, y2] = get_pos(idx2);
    return abs(x1 - x2) + abs(y1 - y2);
}

/**
 * @brief 深度优先搜索最长简单路径
 * @param cur 当前所在节点索引
 * @param mask 访问状态掩码，第i位为1表示节点i已在当前路径中
 * @param cur_len 当前路径的节点总数
 * @param path 当前路径的节点序列
 */
void dfs(int cur, uint64_t mask, int cur_len, vector<int>& path) {
    // 到达终点，更新最优解
    if (cur == END_NODE) {
        if (cur_len > max_len) {
            max_len = cur_len;
            best_path = path;
            // 找到覆盖全部64节点的哈密顿路径直接终止程序
            if (max_len == 64) exit(0);
        }
        return;
    }

    // 最优性剪枝：就算把剩下所有未访问节点都走了也超不过已找到的最长路径，直接返回
    int remain_node = 64 - __builtin_popcountll(mask);
    if (cur_len + remain_node <= max_len) return;

    // 筛选所有未访问的邻接节点，按到终点的曼哈顿距离降序排序，优先走远路快速收敛最优解
    vector<int> next_nodes;
    for (int nxt : adj[cur]) {
        if (!(mask & (1ULL << nxt))) {
            next_nodes.push_back(nxt);
        }
    }
    sort(next_nodes.begin(), next_nodes.end(), [&](int a, int b) {
        return manhattan(a, END_NODE) > manhattan(b, END_NODE);
    });

    // 递归搜索+回溯
    for (int nxt : next_nodes) {
        path.push_back(nxt);
        dfs(nxt, mask | (1ULL << nxt), cur_len + 1, path);
        path.pop_back();
    }
}

int main() {
    // 此处替换为你自己定义的所有边即可，示例：添加(0,0)->(0,1)的有向边
    // adj[get_idx(0,0)].push_back(get_idx(0,1));

    vector<int> start_path;
    int start_node = get_idx(0, 0);
    start_path.push_back(start_node);
    dfs(start_node, 1ULL << start_node, 1, start_path);

    // 输出结果
    cout << "最长路径节点数：" << max_len << endl;
    cout << "路径坐标序列：" << endl;
    for (int idx : best_path) {
        auto [x, y] = get_pos(idx);
        cout << "(" << x << "," << y << ") ";
    }
    cout << endl;
    return 0;
}

• 你只需要把原有代码中定义的所有有向边，按照adj[起点索引].push_back(终点索引)的格式填充到邻接表中即可，不需要修改边的方向定义。
• 若你的图是常规网格结构（每个节点出度2~4），上述代码在普通消费级CPU上运行时间不会超过10秒；如果边密度较高，可以额外增加可达性预处理：提前BFS预处理每个节点到{7,7}的可达性，搜索时如果邻接节点不可达终点直接跳过，能进一步压缩搜索时间。
• 不要尝试用Bellman-Ford类算法求解该问题：Bellman-Ford仅支持无正权环图的最长路径（允许重复走节点），一旦存在环就会出现无限绕环的情况，和简单路径（节点不重复）的需求完全不匹配。

内容的提问来源于stack exchange，提问作者dawidsk12345