生成樹最短路徑算法 Java 實現：從鄰接表到遞歸回溯的完整方案

生成樹（Spanning Tree）中任意兩節點路徑唯一，但廣義「生成圖」可能含環。本文實現基於鄰接表的 Dijkstra 算法，支援動態添加/刪除邊的增量更新，適用於網絡路由、拓撲分析場景。

核心數據結構

// 邊定義
class Edge {
    String from, to;
    int cost;
    Edge(String from, String to, int cost) { this.from=from; this.to=to; this.cost=cost; }
}

// 圖：鄰接表 Map<節點, List<邊>>
class Graph {
    Map> adj = new HashMap<>();
    void addEdge(String u, String v, int w) {
        adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new Edge(u, v, w));
        adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new Edge(v, u, w)); // 無向圖
    }
    void removeEdge(String u, String v) { /* 從兩側列表移除 */ }
}

Dijkstra 算法（優先隊列優化）

class ShortestPath {
    private final Graph graph;
    private Map dist;
    private Map prev; // 前驅節點，用於回溯

    public ShortestPath(Graph graph) { this.graph = graph; }

    public List findPath(String src, String dst) {
        dist = new HashMap<>();
        prev = new HashMap<>();
        PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.dist));
        dist.put(src, 0);
        pq.offer(new Node(src, 0));
        Set visited = new HashSet<>();

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (visited.contains(cur.id)) continue;
            visited.add(cur.id);
            if (cur.id.equals(dst)) break;

            for (Edge e : graph.adj.getOrDefault(cur.id, Collections.emptyList())) {
                if (visited.contains(e.to)) continue;
                int nd = cur.dist + e.cost;
                if (nd < dist.getOrDefault(e.to, Integer.MAX_VALUE)) {
                    dist.put(e.to, nd);
                    prev.put(e.to, cur.id);
                    pq.offer(new Node(e.to, nd));
                }
            }
        }
        return buildPath(src, dst);
    }

    private List buildPath(String src, String dst) {
        List path = new ArrayList<>();
        if (!dist.containsKey(dst)) return path; // 不可達
        for (String at = dst; at != null; at = prev.get(at)) path.add(at);
        Collections.reverse(path);
        return path;
    }
    static class Node { String id; int dist; Node(String id, int d) { this.id=id; this.dist=d; } }
}

動態路由表維護策略

文中提到的「每次問鄰居」屬於**按需計算**，但未緩存會導致重複計算。工程實踐建議：

1. 緩存 Map>（源 → 目標 → 下一跳/代價）。
2. 拓撲變更發布事件，失效相關緩存（或標記版本號）。
3. 定時全量重算作為兜底，防止增量邏輯 Bug 導致不一致。

測試用例

Graph g = new Graph();
g.addEdge("A", "B", 1);
g.addEdge("A", "C", 1);
g.addEdge("B", "D", 1);
g.addEdge("C", "D", 1);
g.addEdge("D", "E", 1);

ShortestPath sp = new ShortestPath(g);
System.out.println(sp.findPath("A", "E")); // [A, B, D, E] 或 [A, C, D, E] (代價相同)
System.out.println(sp.findPath("A", "D")); // [A, B, D] 或 [A, C, D]

擴展：約束最短路徑

• 帶權節點（經過節點有成本） → 將節點權重轉移到邊上。
• 多約束（延遲、帶寬、跳數） → 多目標優化，帕累托前沿或加權和標量化。
• 負權邊 → Bellman-Ford 或 SPFA（網絡路由通常無負權）。