每日算法 — 使用java实现车票之旅：Yen算法与边不相交多路径调度

为什么这个游戏天生是图论题

车票之旅（Ticket to Ride）的桌面版本质上是一张边带颜色的图：欧洲地图上的每座城市是一个顶点，城市间的铁路连接是边，每条边有 1~3 个槽位（槽位填满即被某个玩家独占），不同颜色对应不同颜色的车票卡。

玩家的核心动作是”用某种颜色的卡组合，占下一条边”。而任务卡给出的是”从城市 A 到城市 B 的路线”——一旦完成奖励分数，一旦没完成扣分。游戏后期的紧张感全部来自一个图论事实：

你想走的那条最短路，可能已经被对手占了；而当你想换一条路时，你需要的恰恰是次短路、第三短路。

所以一个有用的车票之旅 AI 需要解决两件事：

1. 枚举 k 条最短路径（k 最短路径问题，KSP）；
2. 当中间边被占满时，求出边不相交的替代路径集合。

本文用 Yen 算法做主引擎，用边不相交的贪心裁剪做后处理。这两个组件在游戏里就是”路线规划 + 资源抢占”的数学抽象。

图的建模

package com.example.ticket;

import java.util.*;

/** 带"槽位容量"的加权无向图（车票之旅的铁路网络）。 */
public final class RailGraph {
    public static final class Edge {
        public final int to;
        public final double w;          // 代价：1 节车 = 1.0（或按颜色稀缺度加权）
        public final int id;            // 全局边 id，用于"封禁"
        public final int capacity;      // 槽位数 1~3
        public int usedSlots = 0;

        Edge(int to, double w, int id, int capacity) {
            this.to = to; this.w = w; this.id = id; this.capacity = capacity;
        }
        public boolean available() { return usedSlots < capacity; }
    }

    private final List<List<Edge>> adj;
    private final Map<String, Integer> cityId = new HashMap<>();
    private final List<String> cityName = new ArrayList<>();
    private int edgeCounter = 0;

    public RailGraph() { adj = new ArrayList<>(); }

    public int addCity(String name) {
        cityId.put(name, cityName.size());
        cityName.add(name);
        adj.add(new ArrayList<>());
        return cityName.size() - 1;
    }

    public int city(String name) { return cityId.getOrDefault(name, -1); }
    public String name(int id)   { return cityName.get(id); }
    public int n()               { return adj.size(); }
    public List<Edge> edgesOf(int u) { return adj.get(u); }

    /** 添加一条双向铁路边（两个方向共享同一个 edge id 与槽位计数）。 */
    public int addRail(String a, String b, double w, int capacity) {
        int u = city(a), v = city(b);
        int id = edgeCounter++;
        Edge e1 = new Edge(v, w, id, capacity);
        Edge e2 = new Edge(u, w, id, capacity);   // 反向引用同一 id
        adj.get(u).add(e1);
        adj.get(v).add(e2);
        return id;
    }
}

注意双向上加了两条 Edge，但共享同一个 id 与容量。这样在”封禁边”时按 id 过滤即可对称封禁，避免”只封了一个方向”的经典 bug。

Dijkstra 与”边封禁”

Yen 算法反复需要”在某个图中求最短路，但有若干边被临时禁用”。做法是把封禁集合作为参数传入：

package com.example.ticket;

import java.util.*;

public final class Dijkstra {
    /** 最短路径结果：距离 + 顶点序列 + 边 id 序列。 */
    public static final class Path implements Comparable<Path> {
        public final double dist;
        public final List<Integer> vertices;
        public final List<Integer> edges;

        Path(double d, List<Integer> v, List<Integer> e) {
            dist = d; vertices = v; edges = e;
        }

        @Override public int compareTo(Path o) {
            return Double.compare(dist, o.dist);
        }

        @Override public String toString() {
            return String.format("%.1f via %s", dist, vertices);
        }
    }

    /**
     * @param bannedEdges 需临时禁用的边 id 集合（可为 null）
     * @param bannedNode  需临时禁用的单点（Yen 的根路径排除用，可为 -1）
     */
    public static Path shortest(RailGraph g, int src, int dst,
                                Set<Integer> bannedEdges, int bannedNode) {
        int n = g.n();
        double[] dist = new double[n];
        int[] prevV = new int[n];
        int[] prevE = new int[n];
        Arrays.fill(dist, Double.POSITIVE_INFINITY);
        Arrays.fill(prevV, -1);
        Arrays.fill(prevE, -1);

        boolean[] done = new boolean[n];
        PriorityQueue<double[]> pq =
                new PriorityQueue<>((x, y) -> Double.compare(x[1], y[1]));
        dist[src] = 0;
        pq.add(new double[]{src, 0});

        while (!pq.isEmpty()) {
            double[] cur = pq.poll();
            int u = (int) cur[0];
            if (done[u]) continue;
            done[u] = true;
            if (u == dst) break;

            for (RailGraph.Edge e : g.edgesOf(u)) {
                // 三条过滤：临时封禁边、不可用边（已被占满）、临时封禁点
                if (bannedEdges != null && bannedEdges.contains(e.id)) continue;
                if (!e.available()) continue;
                if (e.to == bannedNode) continue;

                double nd = dist[u] + e.w;
                if (nd < dist[e.to]) {
                    dist[e.to] = nd;
                    prevV[e.to] = u;
                    prevE[e.to] = e.id;
                    pq.add(new double[]{e.to, nd});
                }
            }
        }

        if (dist[dst] == Double.POSITIVE_INFINITY) return null;

        // 回溯
        List<Integer> verts = new ArrayList<>();
        List<Integer> eids = new ArrayList<>();
        int cur = dst;
        while (cur != -1) {
            verts.add(cur);
            int pe = prevE[cur];
            if (pe == -1) break;
            eids.add(pe);
            cur = prevV[cur];
        }
        Collections.reverse(verts);
        Collections.reverse(eids);
        return new Path(dist[dst], verts, eids);
    }
}

使用懒删除 + done[] 标记代替 decrease-key：这是 Java 里性价比最高的写法，代价是堆里可能有重复元素，但省去了索引堆的维护成本。

核心：Yen 算法

Yen 算法的思路是”逐次生成”：

1. 先求第 1 短路 P₁；
2. 对 P₁ 上的每条边 eᵢ（作为”分叉点”）：
3. 把 P₁ 从源点走到该分叉点之前的顶点作为根路径；
4. 封禁根路径上的所有边（不许重复走）；
5. 封禁根路径上除分叉点外的所有顶点（不许绕回）；
6. 在此受限图上求 分叉点 → 终点 的最短路；
7. 拼起来，作为候选放进优先队列；
8. 从候选队列里弹出当前最小、且不重复的路径，作为第 2 短路；再对这条路径重复第 2 步，得到第 3、第 4……

package com.example.ticket;

import java.util.*;

/** Yen 算法：求前 k 条最短（无环）路径。 */
public final class YenKShortest {

    public static List<Dijkstra.Path> kShortest(RailGraph g, int src, int dst, int k) {
        List<Dijkstra.Path> result = new ArrayList<>();
        if (k <= 0) return result;

        // 第 1 短路
        Dijkstra.Path p0 = Dijkstra.shortest(g, src, dst, null, -1);
        if (p0 == null) return result;
        result.add(p0);

        // 候选池：按距离排序，用"边序列"做 key 去重
        PriorityQueue<Dijkstra.Path> candidates = new PriorityQueue<>();
        Set<String> seen = new HashSet<>();
        seen.add(keyOf(p0));

        for (int ki = 1; ki < k; ki++) {
            Dijkstra.Path prevPath = result.get(ki - 1);

            // 对 prevPath 上的每个分叉位置生成候选
            for (int i = 0; i < prevPath.edges.size(); i++) {
                int spurNode = prevPath.vertices.get(i);

                // 根路径：源点 → spurNode
                List<Integer> rootVerts =
                        new ArrayList<>(prevPath.vertices.subList(0, i + 1));
                List<Integer> rootEdges =
                        new ArrayList<>(prevPath.edges.subList(0, i));

                Set<Integer> bannedEdges = new HashSet<>();

                // 已找到的每条路径，只要它的前 i 条边与 rootEdges 相同，
                // 就封禁它的第 i 条边（避免重复生成同一条路径）
                for (Dijkstra.Path p : result) {
                    if (p.edges.size() > i
                            && p.edges.subList(0, i).equals(rootEdges)) {
                        bannedEdges.add(p.edges.get(i));
                    }
                }

                // 受限图上求 spurNode → dst（根路径顶点除起终点外全部禁入）
                Dijkstra.Path spur = shortestWithNodeSet(
                        g, spurNode, dst, bannedEdges, rootVerts);

                if (spur == null) continue;

                // 拼接根路径 + spur
                double rootDist = distanceOf(g, rootEdges);
                List<Integer> fullVerts = new ArrayList<>(rootVerts);
                for (int m = 1; m < spur.vertices.size(); m++) {
                    fullVerts.add(spur.vertices.get(m));
                }
                List<Integer> fullEdges = new ArrayList<>(rootEdges);
                fullEdges.addAll(spur.edges);

                Dijkstra.Path full =
                        new Dijkstra.Path(rootDist + spur.dist, fullVerts, fullEdges);

                String k2 = keyOf(full);
                if (!seen.contains(k2)) {
                    seen.add(k2);
                    candidates.add(full);
                }
            }

            if (candidates.isEmpty()) break;
            result.add(candidates.poll());
        }
        return result;
    }

    /** 根路径距离 = 沿边权重求和。 */
    private static double distanceOf(RailGraph g, List<Integer> edgeIds) {
        double sum = 0;
        for (int id : edgeIds) sum += weightOf(g, id);
        return sum;
    }

    private static double weightOf(RailGraph g, int edgeId) {
        for (int u = 0; u < g.n(); u++) {
            for (RailGraph.Edge e : g.edgesOf(u)) {
                if (e.id == edgeId) return e.w;
            }
        }
        return 0;
    }

    /** 带"顶点集合禁入 + 边集合禁入"的最短路。 */
    static Dijkstra.Path shortestWithNodeSet(RailGraph g, int src, int dst,
                                             Set<Integer> bannedEdges,
                                             List<Integer> bannedNodes) {
        int n = g.n();
        double[] dist = new double[n];
        int[] prevV = new int[n], prevE = new int[n];
        Arrays.fill(dist, Double.POSITIVE_INFINITY);
        Arrays.fill(prevV, -1);
        Arrays.fill(prevE, -1);

        Set<Integer> nodeBan = new HashSet<>(bannedNodes);
        nodeBan.remove(src);       // 起点不能被自己禁掉
        nodeBan.remove(dst);       // 终点也不能禁

        boolean[] done = new boolean[n];
        PriorityQueue<double[]> pq =
                new PriorityQueue<>((x, y) -> Double.compare(x[1], y[1]));
        dist[src] = 0;
        pq.add(new double[]{src, 0});

        while (!pq.isEmpty()) {
            double[] cur = pq.poll();
            int u = (int) cur[0];
            if (done[u]) continue;
            done[u] = true;
            if (u == dst) break;
            for (RailGraph.Edge e : g.edgesOf(u)) {
                if (bannedEdges != null && bannedEdges.contains(e.id)) continue;
                if (!e.available()) continue;
                if (nodeBan.contains(e.to)) continue;
                double nd = dist[u] + e.w;
                if (nd < dist[e.to]) {
                    dist[e.to] = nd; prevV[e.to] = u; prevE[e.to] = e.id;
                    pq.add(new double[]{e.to, nd});
                }
            }
        }

        if (dist[dst] == Double.POSITIVE_INFINITY) return null;

        List<Integer> verts = new ArrayList<>(), eids = new ArrayList<>();
        int cur = dst;
        while (cur != -1) {
            verts.add(cur);
            if (prevE[cur] == -1) break;
            eids.add(prevE[cur]);
            cur = prevV[cur];
        }
        Collections.reverse(verts);
        Collections.reverse(eids);
        return new Dijkstra.Path(dist[dst], verts, eids);
    }

    private static String keyOf(Dijkstra.Path p) {
        StringBuilder sb = new StringBuilder();
        for (int e : p.edges) sb.append(e).append(',');
        return sb.toString();
    }
}

复杂度

Yen 的复杂度是 O(k · n · (m + n log n))：每次生成新路径要对前一条路径上的最多 n 个分叉点各跑一次 Dijkstra。对车票之旅的地图规模（欧洲版约 47 座城市、约 90 条边），k = 10 时总耗时在毫秒级 —— 完全可以在每回合决策时现算。

车票之旅的实战决策：任务规划

有了 k 短路列表后，任务规划变成一个带资源竞争的分配问题：

package com.example.ticket;

import java.util.*;

/**
 * 任务规划器：给定若干"任务卡"（起点 → 终点），
 * 计算一组代价最小、且尽量不共享边的路径组合。
 */
public final class RoutePlanner {

    public static final class Ticket {
        public final int from, to;
        public Ticket(int a, int b) { from = a; to = b; }
    }

    /**
     * 贪心 + 重排：按任务"稀缺度"排序，逐个用 Yen 找 k 条候选，
     * 选代价最低（距离 + 重叠惩罚）的一条。
     * @param colorBlocked 对手已封锁的边 id 集合
     */
    public static Map<Ticket, Dijkstra.Path> plan(
            RailGraph g, List<Ticket> tickets, int k, Set<Integer> colorBlocked) {

        // 稀缺度 = 该任务的最短路长度（越长越难，越要先抢资源）
        tickets.sort((a, b) -> {
            Dijkstra.Path pa = Dijkstra.shortest(g, a.from, a.to, colorBlocked, -1);
            Dijkstra.Path pb = Dijkstra.shortest(g, b.from, b.to, colorBlocked, -1);
            double da = pa == null ? Double.MAX_VALUE : pa.dist;
            double db = pb == null ? Double.MAX_VALUE : pb.dist;
            return Double.compare(db, da);    // 长任务优先
        });

        Map<Ticket, Dijkstra.Path> assigned = new LinkedHashMap<>();
        Set<Integer> reservedEdges = new HashSet<>();

        for (Ticket t : tickets) {
            List<Dijkstra.Path> cands = YenKShortest.kShortest(g, t.from, t.to, k);
            if (cands.isEmpty()) continue;

            Dijkstra.Path best = null;
            double bestCost = Double.MAX_VALUE;
            for (Dijkstra.Path p : cands) {
                int overlap = 0, blocked = 0;
                for (int e : p.edges) {
                    if (reservedEdges.contains(e)) overlap++;
                    if (colorBlocked.contains(e)) blocked++;
                }
                if (blocked > 0) continue;     // 触碰对手封锁区直接淘汰

                // 代价 = 距离 + 重叠惩罚（共享一条边意味着要抢两个槽位）
                double cost = p.dist + 1.5 * overlap;
                if (cost < bestCost) { bestCost = cost; best = p; }
            }
            if (best != null) {
                assigned.put(t, best);
                reservedEdges.addAll(best.edges);
            }
        }
        return assigned;
    }
}

关键在 cost = p.dist + 1.5 * overlap 这一行：同一条边的两个槽位需要两套车票卡，所以重叠的边际成本高于”多走一段路”。这个系数可以通过模拟对局调参，1.5 是实践里比较稳定的取值。

为什么还需要”边不相交”视角

Yen 给的是”距离意义上的 k 短路”，它们彼此高度重叠（前 k 短路常常共享大部分边）。但车票之旅里两个玩家同时抢同一条线时，槽位见底的速度比想象中快。因此第二个组件是边不相交路径（edge-disjoint paths）——著名的 Suurballe 算法能在 O(m log n) 内求出两点间两条完全不共享边的最短路，比”跑两次 Yen 再过滤”快得多。

工程折中做法（也是本文推荐的）：

1. 用 Yen 拿到 k 条候选（快、通用、支持封禁）；
2. 加一条硬过滤：从候选里贪心挑出彼此边不相交的子集（按距离升序，每次选不与已选集合冲突的第一条）；
3. 若候选凑不出足够条，再对”必须共享”的位置计算重复代价，交给 RoutePlanner 决策。

/** 从候选路径集合中贪心挑出边不相交的子集。 */
public static List<Dijkstra.Path> edgeDisjointSubset(
        List<Dijkstra.Path> cands, int max) {
    List<Dijkstra.Path> out = new ArrayList<>();
    Set<Integer> used = new HashSet<>();
    for (Dijkstra.Path p : cands) {
        boolean conflict = false;
        for (int e : p.edges) if (used.contains(e)) { conflict = true; break; }
        if (!conflict) {
            out.add(p);
            used.addAll(p.edges);
            if (out.size() >= max) break;
        }
    }
    return out;
}

可运行的入口

package com.example.ticket;

import java.util.*;

public final class Main {
    public static void main(String[] args) {
        RailGraph g = new RailGraph();
        g.addCity("巴黎");      // 0
        g.addCity("伦敦");      // 1
        g.addCity("柏林");      // 2
        g.addCity("维也纳");    // 3
        g.addCity("罗马");      // 4
        g.addCity("巴塞罗那");  // 5

        g.addRail("巴黎", "伦敦", 3.0, 2);
        g.addRail("巴黎", "柏林", 4.0, 2);
        g.addRail("巴黎", "巴塞罗那", 5.0, 1);
        g.addRail("柏林", "维也纳", 3.0, 2);
        g.addRail("维也纳", "罗马", 5.0, 1);
        g.addRail("巴塞罗那", "罗马", 8.0, 1);
        g.addRail("巴黎", "维也纳", 6.0, 1);

        int paris = g.city("巴黎"), rome = g.city("罗马");

        System.out.println("=== 前 4 条最短路径（巴黎 → 罗马）===");
        List<Dijkstra.Path> paths = YenKShortest.kShortest(g, paris, rome, 4);
        for (int i = 0; i < paths.size(); i++) {
            Dijkstra.Path p = paths.get(i);
            StringBuilder sb = new StringBuilder();
            for (int v : p.vertices) sb.append(g.name(v)).append(" ");
            System.out.printf("P%d: dist=%.1f  edges=%d  path=%s%n",
                    i + 1, p.dist, p.edges.size(), sb.toString().trim());
        }

        System.out.println("\n=== 边不相交子集（最多 2 条）===");
        List<Dijkstra.Path> disjoint = edgeDisjointSubset(paths, 2);
        for (Dijkstra.Path p : disjoint) System.out.println("  " + p);

        System.out.println("\n=== 封禁 P1 的第一条边，看备选如何变化 ===");
        Set<Integer> banned = new HashSet<>();
        if (!paths.isEmpty() && !paths.get(0).edges.isEmpty())
            banned.add(paths.get(0).edges.get(0));
        System.out.println("  " + Dijkstra.shortest(g, paris, rome, banned, -1));

        System.out.println("\n=== 任务规划 ===");
        List<RoutePlanner.Ticket> tickets = List.of(
                new RoutePlanner.Ticket(g.city("伦敦"), g.city("罗马")),
                new RoutePlanner.Ticket(g.city("巴黎"), g.city("维也纳")));
        Map<RoutePlanner.Ticket, Dijkstra.Path> plan =
                RoutePlanner.plan(g, tickets, 5, Collections.emptySet());
        for (var e : plan.entrySet())
            System.out.printf("  %s→%s : %s%n",
                    g.name(e.getKey().from), g.name(e.getKey().to), e.getValue());
    }
}

运行输出会直观展示三件事：短路之间的高度重叠、边不相交子集如何强制算法”绕远”、以及封禁一条边后最短路如何跳到另一条完全不同的线。

与其他 KSP 算法的对比

Eppstein 在 k 达到 10⁵ 级别才明显胜过 Yen。车票之旅的 k 是 5~10，Yen 的额外开销完全被常数因子吃掉——不要为了”理论最优”引入 Eppstein 的复杂前缀堆结构，这点在游戏 AI 里非常重要。

小结

车票之旅的路线规划是”k 最短路径 + 资源竞争”的组合题。Yen 算法通过”根路径 + 封禁边/点 + 重跑 Dijkstra”的迭代结构提供候选池；RoutePlanner 用重叠惩罚把”距离最小”翻译成”车票卡消耗最小”；edgeDisjointSubset 在最坏情况下提供真正的备选方案。这三层结构同样适用于公交路线规划、备用链路选择，以及任何”最短路可能被占用”的场景。