Skip to main content

Shortest Path

David Liu4/3/26About 5 min

Shortest Path

最短路

简单图：BFS

复杂图：Floyd, Dijkstra, Bellman-ford, SPFA

面试中一般不考复杂图最短路径问题（除了hard）

问最长路径

BFS 是否可以做? 应该用什么算法呢?

图可以分层：动态规划 Dynamic Programming

图不可分层：深度优先搜索 DFS

分层意思是：路径有一定方向性，不能绕圈（DAG），第i层的点只能走到第i+1层不能回到底 i-1 层

哈希表，图中存在环，同一个节点可能重复进入队列，为了避免重复入队，在入队前标记 visited

Java: HashMap / HashSet

Java 队列建议 new ArrayDeque (链表比数组慢)

简单图

所有边只有一种固定费用，

在任何情况下，队列中只会含有dist值为d和d+1的点，且 dist 值为d的一定排在值为 d+1 的点前面（即 BFS 的两段性），实现了队列的有序性，而无需使用优先队列

Word Ladder

给出两个单词(start和end)和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。

Knight Shortest Path

简单图最短路径，八个方向坐标变换

0/1图

所有边只有两种费用：

  • 0: 无费用
  • 1: 固定费用

从一个节点出发，判断所有的邻居，

  • 0费用连通的节点放在队列首部
  • 1费用连通的节点放在队列尾部

在任何情况下，队列中只会含有 dist 值为 d 和 d+1 的点，且 dis 值为 d 的点一定排在值为 d+1 的点前面（即 BFS 的两段性），实现了队列的有序性，而无需使用优先队列

使网格图至少有一条有效路径的最小代价

给出一个二维图，节点内代表先有方向，问最少改变多少节点原油的方向，使得存在一条从左上角到右下角的路径

int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int minCost(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dist = new int[m * n];
    boolean[] seen = new boolean[m * n];
    Arrays.fill(dist, m * n);
    dist[0] = 0;
    
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offerLast(0);
    
    while (!queue.isEmpty()) {
        int idx = queue.poll();
        if (seen[idx]) {
            continue;
        }
        seen[idx] = true;
        int x = idx / n;
        int y = idx % n;
        for (int i = 0; i < 4; ++i) {
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            int nidx = nx * n + ny;
            int nd = dist[idx] + (grid[x][y] != i + 1? 1: 0);
            
            if (nx >= 0 && nx < m && ny >= 0 && ny < n 
                && nd < dist[nidx]) {
                dist[nidx] = nd;
                if (grid[x][y] == i + 1) { // 原方向
                    queue.offerFirst(nidx);
                } else {  // 需要改变方向，费用1
                    queue.offerLast(nidx);
                }
            }
        }
    }

    return dist[m * n - 1];
}

复杂图

用 Dijkstra 或者 SPFA

负数边问题：面试不考，且竞赛也很少考，主要是负环怎么解决？是否可以一直遍历？（一般不能，否则这样费用就可以无限小了）

限制点不能重复走还是边不能重复走？

  • 点：哈密尔顿路

  • 边：欧拉路

飞行棋I

从数组的最左侧跳到最右侧，只能向右跳，一步跳 1-6 格，有一些格子之间直接飞过去不耗费步数，问最少跳几步

只能向右跳->方向性 ->DP

如果没有这个信息的话，就不能DP但是可以用BFS+

问最少步数，可能是哪些算法?

A. BFS (高概率)
B. DP (次高概率)
C. DFS (几乎没有，最短路上复杂度太大不优)
D. Shortest Path Algorithm (标准最短路面试一般不考)

距离之和最短

矩阵 vs 图

图 Graph

N个点，M条边，M最大是 O(N^2) 的级别，图上BFS时间复杂度 = O(N + M)

  • 说是O(M)问题也不大，因为M一般都比N大

所以最坏情况可能是 O(N^2)

矩阵 Matrix

R行C列，RC个点，RC*2 条边(每个点上下左右4条边，每条边被2个点共享)。 矩阵中BFS时间复杂度 = O(R * C)

矩阵根据题意可以是简单图也可以是复杂图，一般情况下是简单图一步一步走，那个球滚动到边界的题就是一个复杂图，每次滚动的距离不一定，且是一个隐式图

图上的例题

  • 判断一个图是否是一棵树
  • 搜索图中最近值为target的点
  • 无向图连通块

矩阵上的例题

  • 僵尸多少天吃掉所有人
  • 建邮局问题 Build Post Office II

隐式图 Implicit Graph

隐式图：隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件（题意隐含给出），要求按扩展规则应用于扩展结点的过程，找出其他结点，使得隐式图的足够大的一部分编程显式，直到包含目标结点为止。

抽象问题，没有明确告诉什么是点，什么是边：

状态是点、二元关系是边

矩阵是一个非常典型的隐式图，每次都按照拓展规则去找下一个访问的结点

单词接龙也是一个典型的隐式图

隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件（题意隐含给出），要求按扩展规则应用于扩展结点的过程，找出其他结点，使得隐式图的足够大的一部分编程显式，直到包含目标结点为止。

推多米诺

David's Blog
Copyright © 2026 David Liu