C++算法库中最常用的最短路径算法是Dijkstra算法和Floyd-Warshall算法。
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});
}
}
}
}
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];
}
}
}
}
}
这两种算法都能有效地求解最短路径问题,具体选择哪一种算法取决于具体的应用场景和需求。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。