C++故宫最短路径求解
时间: 2024-08-13 11:08:19 浏览: 51
在C++中,解决故宫最短路径问题通常涉及到图论和算法,特别是A*搜索算法、Dijkstra算法或Floyd-Warshall算法。这里我会简单介绍两种常见的方法:
1. Dijkstra算法:适用于带权重的非负边的图,用于寻找从起点到所有其他点的最短路径。Dijkstra算法维护一个优先队列,每次选择当前未访问的节点中距离起点最近的一个,直到所有节点都被访问。C++中可以使用`std::priority_queue`实现这个算法。
```cpp
#include <queue>
#include <vector>
// 假设你有一个邻接矩阵表示的图
std::vector<int> dijkstra(const std::vector<std::vector<int>>& graph, int start) {
// 初始化
std::vector<int> dist(graph.size(), std::numeric_limits<int>::max());
dist[start] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<int>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (int v = 0; v < graph[u].size(); ++v) {
int weight = graph[u][v];
if (weight + dist[u] < dist[v]) {
dist[v] = weight + dist[u];
pq.push({dist[v], v});
}
}
}
return dist;
}
```