利用set在C++中实现Dijkstra算法

Dijkstra算法是一种用于解决单源最短路径问题的经典算法，它可以在带权重的有向图中找到从源节点到所有其他节点的最短路径。

在C++中，可以利用set数据结构来实现Dijkstra算法。set是C++标准库中的一个容器，它按照一定的顺序存储元素，并且不允许重复元素存在。在Dijkstra算法中，我们可以使用set来存储待处理的节点，并根据节点的距离值进行排序。

下面是一个利用set实现Dijkstra算法的示例代码：

#include <iostream>
#include <set>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

// 定义图的邻接表表示
typedef pair<int, int> Edge; // <目标节点, 权重>
typedef vector<vector<Edge>> Graph;

vector<int> dijkstra(const Graph& graph, int source) {
    int n = graph.size();
    vector<int> dist(n, INF); // 存储源节点到各个节点的最短距离
    set<pair<int, int>> pq; // 存储待处理的节点，按照距离值排序

    dist[source] = 0;
    pq.insert({0, source});

    while (!pq.empty()) {
        int u = pq.begin()->second;
        pq.erase(pq.begin());

        for (const auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (dist[u] + weight < dist[v]) {
                pq.erase({dist[v], v});
                dist[v] = dist[u] + weight;
                pq.insert({dist[v], v});
            }
        }
    }

    return dist;
}

int main() {
    int n = 5; // 节点数
    int source = 0; // 源节点

    Graph graph(n);

    // 添加边
    graph[0].push_back({1, 10});
    graph[0].push_back({2, 3});
    graph[1].push_back({2, 1});
    graph[1].push_back({3, 2});
    graph[2].push_back({1, 4});
    graph[2].push_back({3, 8});
    graph[2].push_back({4, 2});
    graph[3].push_back({4, 7});
    graph[4].push_back({3, 9});

    vector<int> shortestDist = dijkstra(graph, source);

    // 输出最短路径
    for (int i = 0; i < n; i++) {
        cout << "Shortest distance from node " << source << " to node " << i << ": " << shortestDist[i] << endl;
    }

    return 0;
}

在上述代码中，我们首先定义了一个Graph类型来表示图的邻接表。然后，我们实现了dijkstra函数来计算从源节点到所有其他节点的最短路径。在函数中，我们使用dist数组来存储最短距离，使用pq set来存储待处理的节点，并根据距离值进行排序。最后，我们在main函数中构建了一个示例图，并输出了最短路径。

这是一个基本的利用set在C++中实现Dijkstra算法的示例。在实际应用中，可以根据具体需求进行优化和扩展。腾讯云提供了丰富的云计算产品和服务，例如云服务器、云数据库、人工智能服务等，可以根据具体场景选择适合的产品来支持和扩展应用。

参考链接：