C++算法库中的最短路径算法

C++算法库中最常用的最短路径算法是Dijkstra算法和Floyd-Warshall算法。

1. Dijkstra算法：Dijkstra算法是一种单源最短路径算法，用于计算一个顶点到其他所有顶点的最短路径。该算法基于贪心策略，通过不断找到距离源点最近的未访问顶点来更新最短路径。

C++标准库中提供了std::priority_queue和std::vector等数据结构来实现Dijkstra算法。以下是Dijkstra算法的伪代码：

void Dijkstra(Graph graph, int source) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[source] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, source});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

2. Floyd-Warshall算法：Floyd-Warshall算法是一种多源最短路径算法，用于计算所有顶点之间的最短路径。该算法基于动态规划的思想，通过逐步更新两个顶点之间的最短路径长度来求解。

C++标准库中提供了std::vector等数据结构来实现Floyd-Warshall算法。以下是Floyd-Warshall算法的伪代码：

void FloydWarshall(Graph graph) {
    int n = graph.size();
    vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
    
    for (int i = 0; i < n; ++i) {
        dist[i][i] = 0;
        for (auto& edge : graph[i]) {
            int j = edge.first;
            int weight = edge.second;
            dist[i][j] = weight;
        }
    }
    
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

这两种算法都能有效地求解最短路径问题，具体选择哪一种算法取决于具体的应用场景和需求。