【数据结构】图-最短路径

文章目录

一、概述
二、单源最短路——Dijkstra 算法
- 1.求解过程
- 2.基本思想
三、Dijkstra 算法步骤
- 1.数据结构
- 2.初始化
- 3.找最小路径
- 4.加入 S 集合
- 5.判断结束
- 6.借东风
四、样例分析
五、完整代码
六、总结
- 算法复杂度分析
- - 1.时间复杂度
  - 2.空间复杂度
- 算法优化
- - 1.链式前向星，优先队列优化
  - - 代码
  - 2.邻接表存储

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 到其他顶点的最短路径。

数据结构：构建邻接矩阵 G.Edge[ ][ ]，有边则存储权值，无边则存储无穷，如图。
初始化：令集合 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[ ] 数组。

找最小：在集合 V-S = {2，3，4，5} 中，用贪心策略来寻找 V-S 集合中 dist[ ] 最小的顶点 t。
加入 S 集合：通过上图，我们得知 t 为 2，4，我们先将 2 加入 S 集合 S = {1，2}，同时更新 V-S = {3，4，5}。
借东风：找到了源点到 t 的最短路径，那么对于集合 V-S 中所有 t 的邻接点 j，都可以借助 t 走捷径。

2 的邻接点只有 5，dist[2] + G.Edge[2][5] = 5 < dist[5] = ∞，因此更新 dist[5] = 5。同时记录 5 的前驱 p[5] = 2。

找最小：在集合 V-S = {3，4，5} 中，用贪心策略来寻找 V-S 集合中 dist[ ] 最小的顶点 t。
加入 S 集合：通过上图，我们得知 t 为 4，我们将 4 加入 S 集合 S = {1，2，4}，同时更新 V-S = {3，5}。
借东风：找到了源点到 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] 。

找最小：在集合 V-S = {3，5} 中，用贪心策略来寻找 V-S 集合中 dist[ ] 最小的顶点 t。
加入 S 集合：通过上图，我们得知 t 为 3 和 5，我们先将 3 加入 S 集合 S = {1，2，3，4}，同时更新 V-S = {5}。
借东风：找到了源点到 t 的最短路径，那么对于集合 V-S 中所有 t 的邻接点 j，都可以借助 t 走捷径。

3 没有邻接点，跳。

找最小：在集合 V-S = {5} 中，用贪心策略来寻找 V-S 集合中 dist[ ] 最小的顶点 t。
加入 S 集合：只剩一个节点了，我们得知 t 为 5，我们将 5 加入 S 集合 S = {1，2，3，4，5}，同时更新 V-S = {}。
算法结束： 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++;
        }
    }
}


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;
        }
    }
}


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;
                }
            }
        }
    }
}


void FindPath(AMGraph G, VexType u) {
    stack 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;
}

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 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);
    }
}

六、总结算法复杂度分析 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 P;
priority_queue, 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;
}

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算法

【数据结构】图-最短路径

C/C++/C#相关栏目本月热门文章