我需要一个构建一个校园交通查询系统程序, 够规划出任意出发地和目的地之间的最短路径的完整代码。要求C++语言并作出实例说明
时间: 2024-11-22 17:38:21 浏览: 25
要创建一个校园交通查询系统,我们通常会选择使用图数据结构(如邻接矩阵或邻接表)来表示道路网络,并利用Dijkstra算法或A*搜索算法来找到两点之间的最短路径。这里我会给出一个简单的Dijkstra算法的实现,因为对于较小的校园地图,这个算法已经足够了。请注意,这只是一个基础示例,实际应用可能需要更复杂的数据结构和优化。
首先,我们需要定义一个`Graph`类,用于存储节点和边:
```cpp
#include <vector>
#include <queue>
class Node {
public:
int id;
double distance; // 初始距离设为无穷大
bool visited = false;
Node(int id) : id(id), distance(std::numeric_limits<double>::max()) {}
};
class Graph {
private:
std::vector<std::vector<Node>> adjList; // 邻接列表
public:
void addEdge(Node& node1, Node& node2, double weight) {
adjList[node1.id].push_back({node2.id, weight});
adjList[node2.id].push_back({node1.id, weight}); // 对称边
}
void dijkstra(const Node& startNode) {
priority_queue<std::pair<double, Node>, std::vector<std::pair<double, Node>>, std::greater<std::pair<double, Node>>> pq;
pq.push({startNode.distance, startNode});
while (!pq.empty()) {
auto current = pq.top();
pq.pop();
if (current.second.visited)
continue;
current.second.visited = true;
for (const auto& neighbor : adjList[current.second.id]) {
const double newDistance = current.first + neighbor.second;
if (newDistance < neighbor.first) {
neighbor.first = newDistance;
pq.push({neighbor.first, neighbor.second});
}
}
}
}
};
```
然后,你可以创建一个主函数来测试这个系统:
```cpp
int main() {
Graph graph;
// 假设我们有三个节点 A(0), B(1), C(2)
Node nodes[] = {Node(0), Node(1), Node(2)};
graph.addEdge(nodes[0], nodes[1], 1); // AB 1单位时间
graph.addEdge(nodes[0], nodes[2], 2); // AC 2单位时间
graph.addEdge(nodes[1], nodes[2], 3); // BC 3单位时间
// 开始位置
Node startNode = nodes[0];
// 运行Dijkstra
graph.dijkstra(startNode);
// 打印结果,例如从A到C的最短路径
std::cout << "Shortest path from " << startNode.id << " to " << nodes[2].id << ": ";
if (nodes[2].visited) {
std::cout << "Found in " << nodes[2].distance << " units.\n";
} else {
std::cout << "No path found.\n";
}
return 0;
}
```
这个例子展示了如何使用Dijkstra算法找到起点到终点的最短路径。如果你的需求更复杂,比如需要支持实时更新、大规模数据或动态添加/删除路径,那么可能需要考虑使用更高效的数据结构和技术,如优先队列的实现(如堆)、并查集等。
阅读全文