离职交接5天突然被领导叫停，说要让我做主管。。

“成本最小路径”这个名字一听就是 LeetCode 那挂的，十有八九是图论，没跑。先说结论：Dijkstra 算法，是真香！虽然 Bellman-Ford 和 Floyd-Warshall 也能干，但要说主流又高效，在正权图下，Dijkstra 基本就是“祖传解法”。

我之前面试某大厂的时候，就碰上类似的题目：“给你一个图，每条边都有一个权重，问从起点到终点的最小路径成本。”当时是用 Java 写的，没带现成的图类库，只能撸裸的优先队列 + 邻接表，搞得我差点头秃 🤯。

咱们先来点干货，贴一段最精简但又实用的 Dijkstra 实现：

classSolution{
publicintminCostPath(int n, int[][] edges, int src, int dst){
        List<List<int[]>> graph = new ArrayList<>();
for(int i = 0; i < n; i++) graph.add(new ArrayList<>());
for(int[] e : edges) graph.get(e[0]).add(newint[]{e[1], e[2]});

int[] dist = newint[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(newint[]{src, 0});

while(!pq.isEmpty()) {
int[] cur = pq.poll();
int u = cur[0], d = cur[1];
if(u == dst) return d;
if(d > dist[u]) continue;

for(int[] nei : graph.get(u)) {
int v = nei[0], w = nei[1];
if(dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.offer(newint[]{v, dist[v]});
                }
            }
        }
return -1;
    }
}

这段代码核心思路很朴素：用一个最小堆维护“当前最短路径的候选集合”，每次取出最短的路径进行拓展。因为用了 PriorityQueue，所以在 Java 中效率还不错，能打过大部分场景。

讲真，别看这个代码不到 30 行，但实际用起来坑还真不少——

比如：

1. 有些图会给你双向边，有些只给单向的，不看清题就直接建图，很容易跪。
2. dist[u] 更新判断不要写反了，不然优先队列会加很多冗余点，甚至死循环。
3. 图的点编号从0开始，还是1开始，这点我就栽过好几回。

还有更坑的：带“中转次数限制”的变种，这就不能裸跑 Dijkstra 了，得加状态记录。比如 LC 上那道“ K 次中转内最便宜的航班”，就得在 Dijkstra 里塞一个 hops 限制，或者干脆改 BFS + 剪枝。

说个离谱的事儿，有一回我碰到一题，图的数据量特别大，然后我以为能跑得动，就直接开了 Dijkstra。结果超时得飞起。后来一分析，发现是稀疏图且 K 很小，改成 A* 加个估价函数，秒过。写代码真的不能死脑筋。

其实不只是图论，整个算法学习都有点像练武功，一开始觉得动态规划好强，然后你慢慢接触到拓扑排序、线段树、堆优化、LCA...你就会发现，这些都是“兵器库”里的工具，你得知道什么时候用哪一把。

哦对，说到 Dijkstra，也别忘了它一个致命缺陷：不能处理负权边！这是基础但超级容易被忽略的点。Java 初学者容易踩坑，用着还挺顺，结果一道题突然挂了——原因：某条边权重是负的。建议一看到负权，就直接考虑 Bellman-Ford 或者 SPFA。

最后，如果你准备面试或者刷题，就认准这几招图论大法：

• Dijkstra：正权图最短路径，优先队列贼香。
• Bellman-Ford：负权图救命稻草，能检测负环。
• Floyd-Warshall：多源最短路径，全图对比一网打尽，适合点数小。
• BFS/DFS：不带权的最短路径 or 可达性判断，亲儿子级别的基础操作。

刷多了之后你会发现，其实这些算法并不难，关键是——熟。就跟写业务代码一样，写多了你自然知道哪个场景用哪套套路。

那这次就写到这儿。说实话，路径问题里“最小成本”这个标签很常见，但一旦换个名字，比如“最短时间”、“最低风险”，它本质上还是同一套东西。你能识破这些“换皮怪”，基本就能刷图题如切菜啦 🥗

话说回来，你们最近刷题都在攻哪类题？是不是图论这块卡得比较多