Dijkstra模板

(Updated: )
面试 › 数据结构与算法

Dijkstra算法是一种用于解决单源最短路径问题的图算法，它可以找到从一个起始节点到其他所有节点的最短路径。该算法被广泛应用于网络路由、地图导航等领域。

下面是Dijkstra算法的基本步骤：

  1. 初始化：将起始节点的距离设置为0，将其他节点的距离设置为无穷大（表示尚未计算得到最短路径），将起始节点标记为当前节点。

  2. 迭代过程：重复执行以下步骤，直到所有节点都被标记为已访问（即已找到最短路径）：
    a. 从未访问的节点中选择距离最小的节点作为当前节点。
    b. 对于当前节点的每个邻接节点，计算通过当前节点到达邻接节点的路径长度之和。如果该路径长度小于邻接节点的当前最短路径长度，则更新最短路径长度为新的路径长度。
    c. 标记当前节点为已访问。

  3. 输出最短路径：根据最终的最短路径长度，可以得到从起始节点到达其他节点的最短路径。如果需要还原具体的路径，可以使用额外的数据结构（如前驱节点数组）来记录最短路径的信息。

Dijkstra算法的核心思想是通过逐步扩展路径来寻找最短路径。在迭代过程中，每次选择距离最小的节点作为当前节点，并通过当前节点更新邻接节点的最短路径长度。该过程保证了每个节点被访问时，其最短路径长度已经确定，因此算法能够找到最短路径。

Dijkstra算法的时间复杂度取决于图的表示方式。在使用二叉堆等高效数据结构实现的情况下，时间复杂度可以达到O((V + E) log V)，其中V表示节点数，E表示边数。然而，Dijkstra算法对于存在负权边的图不适用。在处理有负权边的情况下，需要使用其他算法，如Bellman-Ford算法或者使用Dijkstra算法的变种，如使用堆优化的Dijkstra算法（Dijkstra with heap optimization）或使用双向搜索的Dijkstra算法（Bidirectional Dijkstra）。

Java模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.Arrays;
import java.util.Scanner;

public class Solution {

    static final int INF = Integer.MAX_VALUE;
    static int[][] cost = null;
    static int[] dis = null;
    static boolean[] vis = null;
    /**
     * n nodes
     * m edges
     * s start node
     * t target node
     */
    static int n, m, s, t;
    /**
     * u start
     * v end
     * w weight
     */
    static int u, v, w;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        cost = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cost[i], INF);
        }
        for (int i = 0; i < m; i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            w = scanner.nextInt();
            cost[u][v] = w;
        }
        s = 0;
        t = n - 1;
        dijkstra();
        System.out.println(dis[t]);

    }

    public static void dijkstra() {
        dis = new int[n];
        vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            dis[i] = INF;
            vis[i] = false;
        }
        dis[s] = 0;
        for (; ; ) {
            int k = -1;
            int min = INF;
            // 寻找最小值的偏移
            for (int j = 0; j < n; j++) {
                if (!vis[j] && dis[j] < min) {
                    min = dis[j];
                    k = j;
                }
            }
            // 已经全部访问过了
            if (k == -1) {
                break;
            }
            // 访问过的打上标记
            vis[k] = true;
            for (int j = 0; j < n; j++) {
                if (!vis[j] && cost[k][j] != INF && dis[k] + cost[k][j] < dis[j]) {
                    dis[j] = dis[k] + cost[k][j];
                }
            }
        }
    }
}

数据测试：

1
2
3
4
5
6
7
8
9
4
4
0 1 6
0 2 4
1 3 3
2 3 1
5

进程已结束,退出代码0