带环有向加权图中最大化访问节点数的最小路径成本求解

问题核心定义 #

给定带环有向加权图 (G=(V,E))、起点 (s)，对每个节点 (v \in V)，需找到：

1. 从 (s) 到 (v) 的所有路径中，访问不同节点数量最多的路径集合；
2. 在该集合中，选取路径总成本最小的那条，记录其成本。
   最终返回以节点ID为键、对应路径成本为值的Map。

注：绕环重复访问已遍历节点的路径，不会增加「访问节点数」，因此无需考虑（这类路径无法提升节点数优先级，且成本只会更高或不变）。

算法设计思路 #

采用动态规划+状态扩展的方式，核心是为每个节点维护「已访问节点数-最小成本」的映射，优先扩展节点数更大的状态，再在同节点数下优化成本：

1. 状态定义：
   用 dp[v][k] 表示从起点 (s) 到节点 (v)、恰好访问了 (k) 个不同节点的最小成本。其中 (k) 的取值范围为 (1 \sim |V|)（最多访问所有节点）。

2. 初始化：

   • 起点 (s) 的初始状态：dp[s][1] = 0（仅访问自身，成本为0）；
   • 所有其他节点的所有 (k) 值初始化为无穷大（表示不可达）。

3. 状态扩展与更新：
   遍历所有节点的状态，对每个节点 (u) 的每个有效状态 (k_u)（即 dp[u][k_u] 不为无穷大），遍历其所有出边 (u \rightarrow v)（权重为 (w)）：

   • 若 (v) 未被包含在 (u) 对应状态的已访问节点集合中，可生成 (v) 的新状态 (k_u+1)；
   • 若 dp[u][k_u] + w < dp[v][k_u+1]，则更新 dp[v][k_u+1] 为该更小值。

4. 结果提取：
   对每个节点 (v)，找到其所有有效 (k) 中的最大值 (k_{max})，对应的 dp[v][k_{max}] 即为该节点的目标成本；若所有 (k) 均为无穷大，则表示该节点不可达。

Java核心实现伪代码 #

import java.util.*;

public class MaxNodeMinCostPath {
    // 图的存储：key为起点节点，value为(终点节点, 权重)的列表
    private Map<Integer, List<Pair<Integer, Integer>>> graph;
    private int totalNodes;

    public MaxNodeMinCostPath(Map<Integer, List<Pair<Integer, Integer>>> graph, int totalNodes) {
        this.graph = graph;
        this.totalNodes = totalNodes;
    }

    public Map<Integer, Integer> computePaths(int startNode) {
        // dp结构：节点ID -> (已访问节点数k -> 最小成本)
        Map<Integer, Map<Integer, Integer>> dp = new HashMap<>();
        // 初始化所有节点的dp表
        for (int node : graph.keySet()) {
            dp.put(node, new HashMap<>());
            for (int k = 1; k <= totalNodes; k++) {
                dp.get(node).put(k, Integer.MAX_VALUE);
            }
        }
        // 起点初始化
        dp.get(startNode).put(1, 0);

        // 用队列处理状态扩展，避免重复计算
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.add(new Pair<>(startNode, 1));

        // 跟踪每个节点已访问的节点集合，用于判断是否新增节点
        Map<Integer, Map<Integer, Set<Integer>>> visitedNodes = new HashMap<>();
        visitedNodes.put(startNode, new HashMap<>());
        visitedNodes.get(startNode).put(1, new HashSet<>(Collections.singletonList(startNode)));

        while (!queue.isEmpty()) {
            Pair<Integer, Integer> curr = queue.poll();
            int u = curr.getKey();
            int kU = curr.getValue();
            int currCost = dp.get(u).get(kU);
            Set<Integer> uVisited = visitedNodes.get(u).get(kU);

            // 遍历所有出边
            for (Pair<Integer, Integer> edge : graph.getOrDefault(u, Collections.emptyList())) {
                int v = edge.getKey();
                int weight = edge.getValue();
                int newK = kU + 1;

                // 若v未被访问过，才扩展新节点数的状态
                if (!uVisited.contains(v)) {
                    int newCost = currCost + weight;
                    // 如果新成本更小，则更新
                    if (newCost < dp.get(v).get(newK)) {
                        dp.get(v).put(newK, newCost);
                        // 更新访问节点集合
                        visitedNodes.computeIfAbsent(v, k -> new HashMap<>());
                        Set<Integer> newVisited = new HashSet<>(uVisited);
                        newVisited.add(v);
                        visitedNodes.get(v).put(newK, newVisited);
                        queue.add(new Pair<>(v, newK));
                    }
                }
            }
        }

        // 提取最终结果
        Map<Integer, Integer> result = new HashMap<>();
        for (int node : graph.keySet()) {
            Map<Integer, Integer> nodeDp = dp.get(node);
            int maxK = -1;
            int minCost = Integer.MAX_VALUE;
            // 找到最大的k对应的最小成本
            for (Map.Entry<Integer, Integer> entry : nodeDp.entrySet()) {
                int k = entry.getKey();
                int cost = entry.getValue();
                if (cost != Integer.MAX_VALUE) {
                    if (k > maxK) {
                        maxK = k;
                        minCost = cost;
                    } else if (k == maxK && cost < minCost) {
                        minCost = cost;
                    }
                }
            }
            result.put(node, minCost == Integer.MAX_VALUE ? null : minCost);
        }
        return result;
    }

    // 辅助Pair类，替代Java自带的AbstractMap.SimpleEntry
    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() { return key; }
        public V getValue() { return value; }
    }
}

关键注意事项 #

• 环的处理：仅当环包含未访问节点时，才会被纳入状态扩展；若环上节点均已访问，不会增加节点数，因此直接跳过，避免无限循环。
• 状态空间优化：由于 (k) 的最大值为总节点数 (|V|)，状态总数为 (|V|^2)，时间复杂度为 (O(|V| \times |E|))，在常规图规模下可接受。
• 不可达节点：结果中不可达节点的成本设为null，可根据需求调整为特定标识（如无穷大）。

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