• 【数据结构】图-最短路径_Dijkstra 算法（图解、c++、Java）

    文章目录

    GitHub同步更新（已分类）：Data_Structure_And_Algorithm-Review

    公众号：URLeisure 的复习仓库
    公众号二维码见文末

    以下是本篇文章正文内容，下面案例可供参考。

    一、概述

    • 在现实生活中，有很多问题都可以转化为图来解决。
    • 如，计算地图中两地之间的最短路径、网络最小成本布线、工程进度控制等。

    如何求源点到其他各顶点的最短路径？

    • 迪杰斯特拉提出了著名的单源最短路径求解算法 Dijkstra 算法。
    • 艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra，1930年5月11日~2002年8月6日），生于荷兰鹿特丹，计算机科学家。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖。。。。（百度百科）

    二、单源最短路——Dijkstra 算法

    • 给定有向带权图 G = (V，E)，其中每条边的权值是非负实数。给定一个顶点 V ，称为源点。

    • 现在要计算 从源点到其他各个顶点的最短路径长度。

    • 在带权图中，两个顶点的路径长度指它们之间的路径上各边的权值之和。

    • Dijkstra 算法是解决单源最短路径问题的贪心算法。

    1.求解过程

    • 它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径

    2.基本思想

    • 假定源点为 u，顶点集合 V 被划分为两部分：集合 S 和 V-S。
    • 初始时 S 中仅含有源点 u，S 中的顶点到源点的最短路径已经确定，V-S 中的顶点到源点的路径待定。
    • 从源点出发只经过 S 中的点到达 V-S 中的点的路径为特殊路径，用数组 dist[ ] 记录当前每个顶点对应的最短特殊路径长度、

    Dijkstra 算法采用的贪心策略是 选择一条特殊路径，其长度为最短的路径，将其连接的 V-S 中的顶点加入集合 S，同时更新数组 dist[]。一旦 S 包含了所有顶点，dist[] 就是从源点到所有其他顶点之间的最短路径长度。

    三、Dijkstra 算法步骤

    1.数据结构

    • 设置地图的带权邻接矩阵为 G.Edge[ ][ ]；
    • 即如果从源点 u 到顶点 i 有边，就令 G.Edge[u][i] 等于 的权值（u、i 是顶点），否则 G.Edge[u][i] = ∞；
    • 采用一维数组 dist[i] 来记录从源点到顶点 i 的最短路径长度；
    • 采用一维数组 p[i] 来记录最短路径上 i 顶点的前驱。

    2.初始化

    • 令集合 S = {u}；
    • 对于集合 V-S 中的所有顶点 x，初始化 dist[i] = G.Edge[u][i]；
    • 如果源点 u 到顶点 i 有边且相连，初始化 p[i] = u，否则 p[i] = -1。

    3.找最小路径

    • 在集合 V-S 中依照贪心策略来寻找使得 dist[j] 具有最小值的顶点 t，即 dist[t] = min(dist[j])（j 属于 V-S 集合），则顶点 t 就是集合 V-S 中距离源点 u 最近的顶点。

    4.加入 S 集合

    • 将顶点 t 加入集合 S 中，同时更新 V-S。

    5.判断结束

    • 如果集合 V-S 为空，算法结束，否则跳转 → "借东风"。

    6.借东风

    • "找最小路径" 中已经找到了源点 t 的最短路径，那么对于集合 V-S 中所有与顶点 t 相邻的顶点 j，都可以借助 t 走捷径。
    • 如果 dist[j] > dist[t] + G.Edge[t][j]，则 dist[j] = dist[t] + G.Edge[t][j]，记录顶点 j 的前驱为 t，有 p[j] = t，再跳转到 "找最小路径"。

    由此，可求得从源点 u 到图 G 的其余各个顶点的最短路径及长度，也可以通过数组 p[ ] 逆向找到最短路径上经过的顶点。

    四、样例分析

    如图，利用 Dijkstra 算法计算源点 1 到其他顶点的最短路径。

    在这里插入图片描述

    1. 数据结构：构建邻接矩阵 G.Edge[ ][ ]， 有边则存储权值，无边则存储无穷，如图。
      在这里插入图片描述
    2. 初始化：令集合 S = {1} 从 1 号顶点出发，V-S = {2，3，4，5}，对于集合 V-S 中的所有顶点 x，初始化最短距离数组。

    dist[i] 记录从源点到 i 顶点的 最短路径长度。
    p[i] 记录最短路径上 i 顶点的 前驱。

    • dist[i] = G.Edge[1][i] (1 是源点)，dist[1] = 0.
      在这里插入图片描述

    • 初始化 p[ ] 数组。
      在这里插入图片描述

    1. 找最小：在集合 V-S = {2，3，4，5} 中，用贪心策略来寻找 V-S 集合中 dist[ ] 最小的顶点 t。
    2. 加入 S 集合：通过上图，我们得知 t 为 2，4，我们先将 2 加入 S 集合 S = {1，2}，同时更新 V-S = {3，4，5}。
    3. 借东风：找到了源点到 t 的最短路径，那么对于集合 V-S 中所有 t 的邻接点 j，都可以借助 t 走捷径。
    • 2 的邻接点只有 5，dist[2] + G.Edge[2][5] = 5 < dist[5] = ∞，因此 更新 dist[5] = 5。同时记录 5 的前驱 p[5] = 2。
      在这里插入图片描述
    1. 找最小：在集合 V-S = {3，4，5} 中，用贪心策略来寻找 V-S 集合中 dist[ ] 最小的顶点 t。
    2. 加入 S 集合：通过上图，我们得知 t 为 4，我们将 4 加入 S 集合 S = {1，2，4}，同时更新 V-S = {3，5}。
    3. 借东风：找到了源点到 t 的最短路径，那么对于集合 V-S 中所有 t 的邻接点 j，都可以借助 t 走捷径。
    • 4 的邻接点有 1，2，3，5，但在 V-S 集合中的邻接点只有 3，5。
    • 节点 3 ，dist[4] + G.Edge[4][3] = 5 = dist[3]，因此 不更新 dist[3] 。
    • 节点 5 ，dist[4] + G.Edge[4][5] = 8 > dist[5] = 5，因此 不更新 dist[5] 。
    1. 找最小：在集合 V-S = {3，5} 中，用贪心策略来寻找 V-S 集合中 dist[ ] 最小的顶点 t。
    2. 加入 S 集合：通过上图，我们得知 t 为 3 和 5，我们先将 3 加入 S 集合 S = {1，2，3，4}，同时更新 V-S = {5}。
    3. 借东风：找到了源点到 t 的最短路径，那么对于集合 V-S 中所有 t 的邻接点 j，都可以借助 t 走捷径。
    • 3 没有邻接点，跳。
    1. 找最小：在集合 V-S = {5} 中，用贪心策略来寻找 V-S 集合中 dist[ ] 最小的顶点 t。
    2. 加入 S 集合：只剩一个节点了，我们得知 t 为 5，我们将 5 加入 S 集合 S = {1，2，3，4，5}，同时更新 V-S = {}。
    3. 算法结束： V-S = {} 为空时，算法结束。

    在这里插入图片描述

    • 通过 dist[ ] 我们可以得到源点到各个顶点的最短路径长度.
    • 通过 p[ ] 我们可以逆向找到最短路径上经过的节点。

    如： p[5] = 2，即 5 的前驱是 2；p[2] = 1，即 2 的前驱是 1；p[1] = -1，1 没有前驱。所以 从源点 1 到 5 的最短路径为 1 → 2 → 5。

    五、完整代码

    c++代码如下（示例）：

    #include
#include "stack"

using namespace std;

typedef string VexType;

const int MaxVnum = 1e2;
const int INF = 0x3f3f3f3f;
int dis[MaxVnum], p[MaxVnum];
int flag[MaxVnum];

struct AMGraph {
    VexType Vex[MaxVnum];
    int Edge[MaxVnum][MaxVnum];
    int vexnum, edgenum;
};

int LocateVex(AMGraph G, VexType x) {
    for (int i = 0; i < G.vexnum; ++i) {
        if (x == G.Vex[i]) {
            return i;
        }
    }
    return -1;
}

void CreateAMGraph(AMGraph &G) {
    VexType u, v;
    int w;
    cin >> G.vexnum >> G.edgenum;
    for (int i = 0; i < G.vexnum; ++i) {
        cin >> G.Vex[i];
    }
    for (int i = 0; i <= G.vexnum; ++i) {
        for (int j = 0; j <= G.vexnum; ++j)
            G.Edge[i][j] = INF;
    }
    while (G.edgenum--) {
        cin >> u >> v >> w;
        int i = LocateVex(G, u);
        int j = LocateVex(G, v);
        if (i != -1 && j != -1) {
            G.Edge[i][j] = w;
        } else {
            G.edgenum++;
        }
    }
}

/**
 *
 * @param G 邻接矩阵
 * @param u 源点的下标
 */
void Init(AMGraph G, int u) {
    for (int i = 0; i < G.vexnum; ++i) {
        dis[i] = G.Edge[u][i];
        flag[i] = false;
        if (dis[i] == INF) {
            p[i] = -1;
        } else {
            p[i] = u;
        }
    }
}

/**
 *
 * @param G 邻接矩阵
 * @param x 源点
 */
void Dijkstra(AMGraph G, VexType x) {
    int u = LocateVex(G, x);
    Init(G, u);
    dis[u] = 0;
    flag[u] = true;
    for (int i = 0; i < G.vexnum; ++i) {
        int temp = INF;
        int t = u;
        for (int j = 0; j < G.vexnum; ++j) {// 在集合 V-S 中找最小
            if (!flag[j] && dis[j] < temp) {
                t = j;
                temp = dis[j];
            }
        }
        if (t == u) {
            return;
        }
        flag[t] = true;//加入 S 集合

        for (int j = 0; j < G.vexnum; ++j) {//借东风
            if (!flag[j] && G.Edge[t][j] < INF) {
                if (dis[j] > dis[t] + G.Edge[t][j]) {
                    dis[j] = dis[t] + G.Edge[t][j];
                    p[j] = t;
                }
            }
        }
    }
}

/**
 *
 * @param G 邻接矩阵
 * @param u 源点
 */
void FindPath(AMGraph G, VexType u) {
    stack<int> s;
    int x;
    for (int i = 0; i < G.vexnum; ++i) {
        x = p[i];
        if (x == -1 && u != G.Vex[i]) {
            cout << u << "无法到" << G.Vex[i];
            continue;
        }
        while (x != -1) {
            s.push(x);
            x = p[x];
        }
        cout << u << "到" << G.Vex[i] << "的路径为：";
        while (!s.empty()) {
            cout << G.Vex[s.top()] << "---";
            s.pop();
        }
        cout << G.Vex[i] << " " << "距离为：" << dis[i] << endl;
    }
}

int main() {
    AMGraph G;
    VexType u;
    CreateAMGraph(G);
    cin >> u;
    Dijkstra(G, u);
    FindPath(G, u);
    return 0;
}
/*
5 8
1 2 3 4 5
1 2 2
1 3 5
1 4 2
2 5 3
4 1 7
4 5 6
4 2 1
4 3 3
1
 */

    • 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
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151

    java代码如下（示例）：

    import java.util.LinkedList;
import java.util.Scanner;

public class A {
    private static Scanner sc = new Scanner(System.in);
    private static final int MaxVnum = 100;
    private static final int INF = Integer.MAX_VALUE;
    private static boolean[] flag = new boolean[MaxVnum];
    private static int[] dist = new int[MaxVnum];
    private static int[] p = new int[MaxVnum];

    private static class AMGraph {
        String Vex[] = new String[MaxVnum];
        int Edge[][] = new int[MaxVnum][MaxVnum];
        int vexnum, edgenum;
    }

    private static int locateVex(AMGraph g, String x) {
        for (int i = 0; i < g.vexnum; i++) {
            if (g.Vex[i].equals(x)) {
                return i;
            }
        }
        return -1;
    }

    private static void createAMGraph(AMGraph g) {
        String u, v;
        int w;
        g.vexnum = sc.nextInt();
        g.edgenum = sc.nextInt();
        for (int i = 0; i <= g.vexnum; i++) {
            for (int j = 0; j <= g.vexnum; j++)
                g.Edge[i][j] = INF;
        }
        for (int i = 0; i < g.vexnum; i++) {
            g.Vex[i] = sc.next();
        }
        while (g.edgenum-- > 0) {
            u = sc.next();
            v = sc.next();
            w = sc.nextInt();
            int i = locateVex(g, u);
            int j = locateVex(g, v);
            if (i != -1 && j != -1) {
                g.Edge[i][j] = w;
            } else {
                g.edgenum++;
            }
        }
    }

    private static void init(AMGraph g, int u) {
        for (int i = 0; i < g.vexnum; i++) {
            dist[i] = g.Edge[u][i];
            flag[i] = false;
            if (dist[i] == INF) {
                p[i] = -1;
            } else {
                p[i] = u;
            }
        }
    }

    private static void dijkstra(AMGraph g, String x) {
        int u = locateVex(g, x);
        init(g, u);
        dist[u] = 0;
        flag[u] = true;
        for (int i = 0; i < g.vexnum; i++) {
            int temp = INF;
            int t = u;
            for (int j = 0; j < g.vexnum; j++) {
                if (!flag[j] && dist[j] < temp) {
                    temp = dist[j];
                    t = j;
                }
            }
            if (t == u) {
                return;
            }
            flag[t] = true;
            for (int j = 0; j < g.vexnum; j++) {
                if (!flag[j] && g.Edge[t][j] < INF) {
                    if (dist[j] > dist[t] + g.Edge[t][j]) {
                        dist[j] = dist[t] + g.Edge[t][j];
                        p[j] = t;
                    }
                }
            }
        }
    }

    public static void findPath(AMGraph g, String u) {
        LinkedList<Integer> s = new LinkedList<>();
        int x;
        for (int i = 0; i < g.vexnum; i++) {
            x = p[i];
            if (x == -1 && !u.equals(g.Vex[i])) {
                System.out.println(u + "无法到达" + g.Vex[i]);
                continue;
            }
            while (x != -1) {
                s.push(x);
                x = p[x];
            }
            System.out.print(u + "到" + g.Vex[i] + "的路径为：");
            while (!s.isEmpty()) {
                System.out.print(g.Vex[s.pop()] + "---");
            }
            System.out.println(g.Vex[i] + " 距离为：" + dist[i]);
        }
    }

    public static void main(String[] args) {
        AMGraph g = new AMGraph();
        String u;
        createAMGraph(g);
        u = sc.next();
        dijkstra(g, u);
        findPath(g, u);
    }
}
/*
5 8
1 2 3 4 5
1 2 2
1 3 5
1 4 2
2 5 3
4 1 7
4 5 6
4 2 1
4 3 3
1
 */

    • 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
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136

    六、总结

    算法复杂度分析

    1.时间复杂度

    • 在 Dijkstra 算法描述中，一共有 4 个 for 语句，第一个 for 语句（init）执行次数为 n，第二个 for 语句里面嵌套了两个 for 语句，它们的执行次数均为 n，对算法的运行时间贡献最大。

    • 当外层循环标号为 1 时，第三四语句在内层循环的控制下均执行 n 次，外层循环从 1~n。

    • 因此，该语句的执行次数为 n × n = n 2 n×n = n^2 n×n=n2，算法的 时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

    2.空间复杂度

    • 由以上算法可以得出，实现该算法所需要的辅助空间包括为数组 flag，变量 i、j、t 和 temp 所分配的空间。

    • 因此 空间复杂度为 O ( n ) O(n) O(n)。

    算法优化

    1.链式前向星，优先队列优化

    • 第三个 for 语句是在集合 V-S 中寻找距离源点 u 最近的顶点 t，如果穷举需要时间 O ( n ) O(n) O(n)，第三个 for 语句的世家复杂度为 O ( n 2 ) O(n^2) O(n2) 。

    • 如果使用优先队列，则找一个最近顶点需要 O ( l o g n ) O(logn) O(logn) 时间，第三个 for 语句的 时间复杂度为 O ( l o g n ) O(logn) O(logn)。

    代码

    c++代码如下（示例）：

    #include
#include 
#include "queue"

using namespace std;
const int N = 1e3;
const int INF = 0x3f3f3f3f;

int n, m, cnt;
int head[N], dist[N];
bool flag[N];

typedef pair<int, int> P;
priority_queue<P, vector<P>, greater<> > que;

struct Edge {
    int to;
    int next;
    int w;
} e[N];

void Init() {
    memset(head, -1, sizeof head);
    memset(dist, INF, sizeof dist);
    memset(flag, false, sizeof flag);
    cnt = 0;
}

void add(int u, int v, int w) {
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

void Dijkstra(int u) {
    dist[u] = 0;
    que.push(P(0, u));
    while (!que.empty()) {
        P x = que.top();
        que.pop();
        int t = x.second;
        if (flag[t]) {
            continue;
        }
        flag[t] = true;
        for (int i = head[t]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (dist[v] > dist[t] + e[i].w) {
                dist[v] = dist[t] + e[i].w;
                que.push(P(dist[v], v));
            }
        }
    }
}

void Print(int u) {
    for (int i = 1; i <= n; i++) {
        cout << u << "到" << i << "的最短距离为：" << dist[i] << endl;
    }
}

int main() {
    cin >> n >> m;
    Init();
    int u, v, w;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    cin >> u;
    Dijkstra(u);
    Print(u);
    return 0;
}
/*
5 8
1 2 2
1 3 5
1 4 2
2 5 3
4 1 7
4 5 6
4 2 1
4 3 3
1
 */

    • 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
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87

    2.邻接表存储

    • 第四个 for 语句有松弛操作，如果采用邻接矩阵存储图，每次需要执行 n 次，第四个 for 语句 时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

    • 如果采用邻接表存储，则每次执行 t 顶点的度数 x，每个顶点的度数之和为边数 e，第四个 for 语句 时间复杂度为 O ( e ) O(e) O(e)。

    • 对于稀疏图， O ( e ) O(e) O(e) 要比 O ( n 2 ) O(n^2) O(n2) 小。

    关注公众号，感受不同的阅读体验

    请添加图片描述

    下期预告：图的最短路径-Bellman_Ford算法

  • 相关阅读:
    HTTP 响应头Cache-Control
    Java Excel转PDF，支持xlsx和xls两种格式， itextpdf【即取即用】
    word 中添加图片目录、内部链接
    Javascript知识【jQuery选择器】
    [附源码]计算机毕业设计springboot教务管理系统
    京东云开发者｜探寻软件架构的本质，到底什么是架构？
    jmeter-录制脚本
    《AI驱动下的开发者新生态》-2024长沙.NET技术社区活动-诚邀大家报名
    Spring框架-AspectJ配置文件
    基于windows10的pytorch环境部署及yolov8的安装及测试
  • 原文地址：https://blog.csdn.net/weixin_50564032/article/details/125690195