多语言算法代码生成器

下面给出一个可直接运行的 Java 实现，输入为有向图邻接表 Map<Integer, List> 与源点 sourceId，输出为最短距离 Map<Integer, Double> 与前驱 Map<Integer, Integer>。同时提供路径还原与结果校验工具。

实现思路与逻辑简介

• 使用 Dijkstra 算法（最小堆优先队列），在非负权重前提下得到从源点到各节点的最短距离。
• 距离使用 double，初始化为正无穷；源点距离为 0。
• 前驱用于还原最短路径：前驱记录的是到达某节点时的上一个节点。
• 使用惰性删除（从堆取出的条目若不是当前最优距离则跳过）保证效率 O((V+E) log V)。
• 校验包括：源点距离为 0、不可达节点距离为正无穷、从前驱还原的路径距离与计算距离一致，并满足三角不等式。

完整代码

import java.util.*;

/**
 * Dijkstra 最短路（非负权重），输入为邻接表 Map<Integer, List<Edge>> 和源点 sourceId。
 * 输出最短距离与前驱，用于路径还原与调度优化。
 */
public class DijkstraShortestPaths {

    public static final double EPS = 1e-12;

    // 图的边
    public static class Edge {
        public final int to;
        public final double weight;

        public Edge(int to, double weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "->" + to + "(" + weight + ")";
        }
    }

    // 结果封装：最短距离与前驱
    public static class DijkstraResult {
        public final Map<Integer, Double> dist; // 最短距离
        public final Map<Integer, Integer> prev; // 前驱

        public DijkstraResult(Map<Integer, Double> dist, Map<Integer, Integer> prev) {
            this.dist = dist;
            this.prev = prev;
        }
    }

    // 小根堆中的结点条目
    private static class NodeDist {
        int node;
        double dist;
        NodeDist(int node, double dist) {
            this.node = node;
            this.dist = dist;
        }
    }

    /**
     * 计算从 sourceId 出发到各节点的最短距离与前驱。
     * 约束：权重必须非负。
     */
    public static DijkstraResult dijkstra(Map<Integer, List<Edge>> graph, int sourceId) {
        if (graph == null) throw new IllegalArgumentException("graph is null");

        // 收集所有节点（包括仅出现在目标端的节点）
        Set<Integer> nodes = new HashSet<>(graph.keySet());
        for (Map.Entry<Integer, List<Edge>> e : graph.entrySet()) {
            List<Edge> edges = e.getValue();
            if (edges == null) continue;
            for (Edge edge : edges) {
                if (edge == null) continue;
                if (edge.weight < 0) {
                    throw new IllegalArgumentException("Negative edge weight detected from " +
                            e.getKey() + " to " + edge.to + ": " + edge.weight);
                }
                nodes.add(edge.to);
            }
        }
        nodes.add(sourceId);

        // 初始化距离与前驱
        Map<Integer, Double> dist = new HashMap<>();
        Map<Integer, Integer> prev = new HashMap<>();
        for (int v : nodes) {
            dist.put(v, Double.POSITIVE_INFINITY);
        }
        dist.put(sourceId, 0.0);

        // 最小堆（按距离）
        PriorityQueue<NodeDist> pq = new PriorityQueue<>(Comparator.comparingDouble(nd -> nd.dist));
        pq.offer(new NodeDist(sourceId, 0.0));

        while (!pq.isEmpty()) {
            NodeDist cur = pq.poll();
            double bestKnown = dist.getOrDefault(cur.node, Double.POSITIVE_INFINITY);
            if (cur.dist > bestKnown + EPS) {
                // 惰性删除：堆中旧条目
                continue;
            }
            List<Edge> edges = graph.getOrDefault(cur.node, Collections.emptyList());
            for (Edge edge : edges) {
                if (edge == null) continue;
                int v = edge.to;
                double nd = cur.dist + edge.weight;
                double old = dist.getOrDefault(v, Double.POSITIVE_INFINITY);
                if (nd + EPS < old) {
                    dist.put(v, nd);
                    prev.put(v, cur.node);
                    pq.offer(new NodeDist(v, nd));
                }
            }
        }

        return new DijkstraResult(dist, prev);
    }

    /**
     * 从前驱表还原 source->target 的路径。如果 target 不可达，返回空列表。
     */
    public static List<Integer> reconstructPath(Map<Integer, Integer> prev, int source, int target) {
        LinkedList<Integer> path = new LinkedList<>();
        Integer cur = target;
        while (cur != null) {
            path.addFirst(cur);
            if (cur == source) break;
            cur = prev.get(cur);
        }
        if (path.isEmpty() || path.getFirst() != source) return Collections.emptyList();
        return path;
    }

    /**
     * 计算路径总权重（若路径非法或边不存在则返回正无穷）。
     */
    public static double pathWeight(Map<Integer, List<Edge>> graph, List<Integer> path) {
        if (path == null || path.size() <= 1) return 0.0;
        double sum = 0.0;
        for (int i = 0; i + 1 < path.size(); i++) {
            int u = path.get(i), v = path.get(i + 1);
            double w = Double.POSITIVE_INFINITY;
            for (Edge e : graph.getOrDefault(u, Collections.emptyList())) {
                if (e.to == v) {
                    w = e.weight;
                    break;
                }
            }
            if (Double.isInfinite(w)) return Double.POSITIVE_INFINITY;
            sum += w;
        }
        return sum;
        }

    /**
     * 基本校验：
     * - 源点距离为 0
     * - 不可达点距离为正无穷（或在 dist 中缺失也可）；
     * - 从前驱还原的路径合法且其总权重等于 dist。
     * - 任意边 (u->v) 满足 dist[v] <= dist[u] + w（最短路必要条件）。
     */
    public static void validate(Map<Integer, List<Edge>> graph, int source, DijkstraResult res) {
        Objects.requireNonNull(res);
        Objects.requireNonNull(res.dist);
        Objects.requireNonNull(res.prev);

        double sourceDist = res.dist.getOrDefault(source, Double.POSITIVE_INFINITY);
        if (Math.abs(sourceDist - 0.0) > EPS) {
            throw new AssertionError("Source distance is not 0: " + sourceDist);
        }

        // 收集所有节点
        Set<Integer> nodes = new HashSet<>(graph.keySet());
        for (Map.Entry<Integer, List<Edge>> e : graph.entrySet()) {
            for (Edge edge : e.getValue()) nodes.add(edge.to);
        }
        nodes.add(source);

        // 前驱路径一致性与三角不等式检查
        for (int v : nodes) {
            double dv = res.dist.getOrDefault(v, Double.POSITIVE_INFINITY);

            if (!Double.isInfinite(dv)) {
                // 能到达：用前驱还原路径并比对距离
                List<Integer> path = reconstructPath(res.prev, source, v);
                if (path.isEmpty()) {
                    throw new AssertionError("Reachable node without a valid predecessor path: " + v);
                }
                double w = pathWeight(graph, path);
                if (Math.abs(dv - w) > 1e-9) {
                    throw new AssertionError("Distance mismatch at node " + v + ": dist=" + dv + ", pathWeight=" + w);
                }
            }

            // 三角不等式：对所有边 (u->v) 检查 dist[v] <= dist[u] + w
            // 也能间接发现负权或不一致
        }
        for (Map.Entry<Integer, List<Edge>> e : graph.entrySet()) {
            int u = e.getKey();
            double du = res.dist.getOrDefault(u, Double.POSITIVE_INFINITY);
            for (Edge edge : e.getValue()) {
                double dv = res.dist.getOrDefault(edge.to, Double.POSITIVE_INFINITY);
                if (du + edge.weight + 1e-9 < dv) {
                    throw new AssertionError("Triangle inequality violated at edge " + u + "->" + edge.to);
                }
            }
        }
    }

    // 示例：可按需删除或保留
    public static void main(String[] args) {
        Map<Integer, List<Edge>> graph = new HashMap<>();
        addEdge(graph, 1, 2, 2);
        addEdge(graph, 1, 3, 5);
        addEdge(graph, 2, 3, 1);
        addEdge(graph, 2, 4, 2);
        addEdge(graph, 3, 4, 1);
        addEdge(graph, 4, 5, 3);

        int source = 1;
        DijkstraResult res = dijkstra(graph, source);

        System.out.println("Distances:");
        res.dist.entrySet().stream()
                .sorted(Map.Entry.comparingByKey())
                .forEach(e -> System.out.println("  " + e.getKey() + " -> " + e.getValue()));

        System.out.println("Predecessors:");
        res.prev.entrySet().stream()
                .sorted(Map.Entry.comparingByKey())
                .forEach(e -> System.out.println("  " + e.getKey() + " <- " + e.getValue()));

        // 还原 1->5 的路径
        List<Integer> path = reconstructPath(res.prev, source, 5);
        System.out.println("Path 1->5: " + path + ", weight=" + pathWeight(graph, path));

        // 校验
        validate(graph, source, res);
        System.out.println("Validation passed.");
    }

    // 辅助：添加边
    private static void addEdge(Map<Integer, List<Edge>> graph, int u, int v, double w) {
        graph.computeIfAbsent(u, k -> new ArrayList<>()).add(new Edge(v, w));
    }
}

使用说明

• dijkstra(graph, sourceId) 返回 DijkstraResult，包含 dist 和 prev 两个 Map。
• reconstructPath(prev, source, target) 可用于还原最短路径序列，用于调度或路径输出。
• validate(graph, source, result) 可在开发/测试阶段做结果一致性检查。

下面给出完整的 JavaScript 实现与简要说明。该实现返回所有匹配起始下标（递增且无重复），并同时返回构造的前缀表（LPS，最长前后缀表）以便验证。

代码（基于 UTF-16 代码单元匹配，适用于 ASCII 与常见 Unicode 文本的日志场景）：

function kmpSearch(text, pattern) { if (typeof text !== 'string' || typeof pattern !== 'string') { throw new TypeError('text 与 pattern 必须是字符串'); }

const m = pattern.length; const n = text.length; if (m === 0) return { indices: [], lps: [] };

const lps = buildLPS(pattern); const indices = [];

let i = 0; // text 指针 let j = 0; // pattern 指针

while (i < n) { if (text[i] === pattern[j]) { i++; j++; if (j === m) { const start = i - m; indices.push(start); // 查找到一个匹配后，利用 LPS 继续尝试下一个（支持重叠匹配） j = lps[j - 1]; } } else { if (j !== 0) { // 发生不匹配，利用 LPS 回退 pattern 指针 j = lps[j - 1]; } else { // j 已在开头，只能推进 text 指针 i++; } } }

// 断言：每个下标处子串等于 pattern，且结果有序无重复 for (let k = 0; k < indices.length; k++) { const idx = indices[k]; if (text.substr(idx, m) !== pattern) { throw new Error(断言失败：下标 ${idx} 处子串不等于 pattern); } if (k > 0 && indices[k] <= indices[k - 1]) { throw new Error('断言失败：返回的下标未严格递增或有重复'); } }

return { indices, lps };

// 构造 LPS（Longest Prefix Suffix）前缀表 function buildLPS(pat) { const lps = new Array(pat.length).fill(0); let len = 0; // 当前最长前后缀长度 for (let i = 1; i < pat.length; ) { if (pat[i] === pat[len]) { len++; lps[i] = len; i++; } else { if (len !== 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps; } }

// 示例 const text = "ERROR_42: ok; ERROR_42: fail"; const pattern = "ERROR_42"; console.log(kmpSearch(text, pattern)); // 期望输出：{ indices: [0, 14], lps: [...] }

实现思路与逻辑简述：

• 先对模式串 pattern 构造 LPS 前缀表，lps[i] 表示以 i 位置结尾的子串的最长“前缀=后缀”的长度。
• 扫描 text 时，遇到不匹配无需回退 text 指针，利用 LPS 快速定位到 pattern 可继续匹配的位置，从而避免暴力匹配的高复杂度。
• 时间复杂度 O(n + m)，空间复杂度 O(m)。返回所有匹配起始下标以及 LPS 以便验证。

说明：

• 该实现基于 JavaScript 的 UTF-16 索引（即字符串的常规索引）。如文本包含代理对（例如某些 Emoji），返回位置按 JS 字符串索引（代码单元）计数；一般日志与错误码场景可直接使用。若需按 Unicode 码点计数，可在外层将字符串转为码点数组并维护索引映射。