Dijkstra's算法解决了带权图单源最短路径的问题。例如：有n个城市，n个城市间有m条路，每条路开车所用的时间不一样，如果我们要计算两个城市间开车所用时间最短，我们就可以使用Dijkstra's算法。接下来让我们一起看看编程玩家俱乐部的成员们在外太空遇到了什么样的问题，他们又是怎么解决的呢？

1
2
3
4
5
6
7
8
9

接下来我们用C++代码来实现Dijkstra's算法，在这里我们使用了邻接表来保存图的数据。

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

// 结构体Node保存2个数据，一个数据为节点的id，则一个为权值
struct Node {
    int id;
    int w;
};

void dijsktra(vector<Node> g[], bool visited[], int dist[], int start, int n) {
    // 重复n次
    for (int i=0; i<n; i++) {
        
        // 找到dist中最小值的下标
        int min_index = 0;
        int min_dist = INT_MAX;
        for (int k=0; k<n; k++) {
            if (!visited[k] && min_dist > dist[k]) {
                min_index = k;
                min_dist = dist[k];
            }
        }
		
        // 将u设置为处理过
        int u = min_index;
        visited[u] = true;
		
        // 对于每个能从u直接到达的v做以下处理
        for (int j=0; j<g[u].size(); j++) {
            Node v = g[u][j];
            if (!visited[v.id]) {
                if (dist[v.id] > dist[u] + v.w) {
                    dist[v.id] = dist[u] + v.w;
                }
            }
        }
    }
}

int main() {
    // n个顶点（或称结点）
    int n; cin >> n;
    // m条边
    int m; cin >> m;

    // 创建一个vector<Node>数组，即每个成员是一个vector，一共有n个成员
    // g[i]表示顶点i能够直接到达的其他顶点的列表
    // 如果是有权图，则可以使用一个结构体的vector，结构体里设置顶点编号和权值
    vector<Node> g[n];

    // 读入m条边数据，每个数据由2个顶点编号u，v组成，表示u到v的一条边（因为是无向图，同时也是v到u的一条边）
    for (int i=0; i<m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        Node node_v;
        node_v.id = v-1;
        node_v.w = w;
        Node node_u;
        node_u.id = u-1;
        node_u.w = w;
        g[u-1].push_back(node_v);
        g[v-1].push_back(node_u);
    }

    // 创建一个数组记录节点是否处理过
    bool visited[n];
    // dist数组记录从出发点到每个点的最短路径值
    int dist[n];
    for (int i=0; i<n; i++) {
        visited[i] = false;
        dist[i] = INT_MAX;
    }

    int s;
    cin >> s;
    // 将出发点设置为0，因为出发点到出必点不需要消耗任何能量
    dist[s-1] = 0;

    dijsktra(g, visited, dist, s-1, n);

    for (int i=0; i<n; i++) {
        cout << dist[i] << ' ';
    }

    return 0;
}

/* 测试输入数据：
9 14
1 2 40
1 8 80
2 3 80
2 8 110
3 4 70
3 6 40
3 9 20
4 5 90
4 6 140
5 6 10
6 7 20
7 8 10
7 9 60
8 9 70
1
*/

/* 测试输出数据：
0 40 120 190 120 110 90 80 140 
*/

运行上面的代码，我们最后看出从1点（出发点）出发，去2、7、8这3个点消耗能量晶体小于100，这3个点都可以去哦。

看漫画也能学C++？没错！编程玩家俱乐部新推出系列课程《看漫画学C++》，带你用轻松看漫画的方式来学习C++，本课程面向零基础学员，只要坚持学习并多思考和多练习，相信你一定会成为C++的编程高手！如果喜欢本课程，就收藏一下哦，转发给你的小伙伴们，大家一起来学习！

img