图算法：Dijkstra最短路径与拓扑排序的Java实现

Dijkstra最短路径（优先队列优化 O(E log V)）

public class Dijkstra {
    
    static class Edge {
        int to, weight;
        Edge(int to, int weight) { this.to = to; this.weight = weight; }
    }
    
    public int[] shortestPath(List<Edge>[] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        // 优先队列：[距离, 节点]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, start});
        
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int d = cur[0], u = cur[1];
            
            if (d > dist[u]) continue;  // 惰性删除
            
            for (Edge edge : graph[u]) {
                int v = edge.to;
                int newDist = d + edge.weight;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    pq.offer(new int[]{newDist, v});
                }
            }
        }
        return dist;
    }
}

不能处理负权边的原因：

• Dijkstra基于贪心，每次从队列中取当前最短距离的节点，将其标记为已确定最短路径
• 如果有负权边，后面可能出现经过负权边使距离更短的情况，但该节点已被标记确定
• 负权边用Bellman-Ford（O(VE)）或SPFA

拓扑排序（Kahn算法 — BFS）

public class TopologicalSort {
    
    // Kahn算法
    public List<Integer> kahnSort(List<Integer>[] graph) {
        int n = graph.length;
        int[] inDegree = new int[n];
        
        // 计算入度
        for (int u = 0; u < n; u++) {
            for (int v : graph[u]) {
                inDegree[v]++;
            }
        }
        
        // 入度为0的节点入队
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);
            
            for (int v : graph[u]) {
                if (--inDegree[v] == 0) queue.offer(v);
            }
        }
        
        // 如果result.size() != n，说明有环
        return result;
    }
    
    // DFS拓扑排序
    public List<Integer> dfsSort(List<Integer>[] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        boolean[] onPath = new boolean[n];
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                if (hasCycle(graph, i, visited, onPath, result)) {
                    throw new RuntimeException("有环，无法拓扑排序");
                }
            }
        }
        Collections.reverse(result);  // DFS后序添加，需要反转
        return result;
    }
    
    private boolean hasCycle(List<Integer>[] graph, int u, boolean[] visited, 
                              boolean[] onPath, List<Integer> result) {
        if (onPath[u]) return true;   // 发现环
        if (visited[u]) return false;
        
        visited[u] = true;
        onPath[u] = true;
        
        for (int v : graph[u]) {
            if (hasCycle(graph, v, visited, onPath, result)) return true;
        }
        
        onPath[u] = false;
        result.add(u);  // 后序添加
        return false;
    }
}

应用场景

算法	应用
Dijkstra	地图导航、网络路由（OSPF）、物流路径规划
拓扑排序	Maven/Gradle依赖解析、任务调度（Spring Boot自动配置顺序）、课程选修顺序、编译器符号解析