C++算法庫中的最短路徑算法

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

1. Dijkstra算法：Dijkstra算法是一種單源最短路徑算法，用于計(jì)算一個(gè)頂點(diǎn)到其他所有頂點(diǎn)的最短路徑。該算法基于貪心策略，通過不斷找到距離源點(diǎn)最近的未訪問頂點(diǎn)來更新最短路徑。

C++標(biāo)準(zhǔn)庫中提供了std::priority_queue和std::vector等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)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算法是一種多源最短路徑算法，用于計(jì)算所有頂點(diǎn)之間的最短路徑。該算法基于動(dòng)態(tài)規(guī)劃的思想，通過逐步更新兩個(gè)頂點(diǎn)之間的最短路徑長度來求解。

C++標(biāo)準(zhǔn)庫中提供了std::vector等數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)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];
                }
            }
        }
    }
}

這兩種算法都能有效地求解最短路徑問題，具體選擇哪一種算法取決于具體的應(yīng)用場景和需求。