设计一个简单的旅游交通线路查询系统,当输入多个地点和地点间的距离和路费后,计算出最合理的路线规划并输出结果,要求算法的时间复杂度较低,并列出详细的c++代码
时间: 2024-03-20 19:43:56 浏览: 16
好的,下面是一个简单的旅游交通线路查询系统的实现,主要使用Dijkstra算法来计算最短路径。
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <limits>
using namespace std;
class Graph {
public:
void add_edge(char from_node, char to_node, int distance, int cost) {
if (edges_.find(from_node) == edges_.end()) {
edges_[from_node] = {};
}
edges_[from_node][to_node] = {distance, cost};
}
pair<int, vector<char>> dijkstra(char start_node, char end_node) {
unordered_map<char, int> distances;
for (auto& it : edges_) {
distances[it.first] = numeric_limits<int>::max();
}
distances[start_node] = 0;
priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>> pq;
pq.push({0, start_node});
while (!pq.empty()) {
auto [distance, current_node] = pq.top();
pq.pop();
if (distances[current_node] < distance) {
continue;
}
for (auto& it : edges_[current_node]) {
auto neighbor = it.first;
auto neighbor_distance = it.second.first;
auto neighbor_cost = it.second.second;
auto new_distance = distance + neighbor_distance;
auto new_cost = distances[current_node] + neighbor_cost;
if (new_distance < distances[neighbor]) {
distances[neighbor] = new_distance;
pq.push({new_distance, neighbor});
paths_[neighbor] = current_node;
costs_[neighbor] = new_cost;
} else if (new_distance == distances[neighbor] && new_cost < costs_[neighbor]) {
costs_[neighbor] = new_cost;
paths_[neighbor] = current_node;
}
}
}
if (distances[end_node] == numeric_limits<int>::max()) {
return {-1, {}};
}
vector<char> path;
for (char node = end_node; node != start_node; node = paths_[node]) {
path.push_back(node);
}
path.push_back(start_node);
reverse(path.begin(), path.end());
return {distances[end_node], path};
}
private:
unordered_map<char, unordered_map<char, pair<int, int>>> edges_;
unordered_map<char, char> paths_;
unordered_map<char, int> costs_;
};
int main() {
// 构建图
Graph g;
g.add_edge('A', 'B', 10, 100);
g.add_edge('A', 'C', 3, 50);
g.add_edge('B', 'C', 1, 20);
g.add_edge('B', 'D', 2, 10);
g.add_edge('C', 'B', 4, 20);
g.add_edge('C', 'D', 8, 30);
g.add_edge('C', 'E', 2, 60);
g.add_edge('D', 'E', 7, 10);
g.add_edge('E', 'D', 9, 50);
// Dijkstra算法计算最短路径
char start_node = 'A';
char end_node = 'D';
auto [distance, path] = g.dijkstra(start_node, end_node);
// 输出结果
if (distance == -1) {
cout << "No path found from " << start_node << " to " << end_node << endl;
} else {
cout << "The shortest distance from " << start_node << " to " << end_node << " is " << distance << endl;
cout << "The path is ";
for (auto& node : path) {
cout << node << " -> ";
}
cout << endl;
}
return 0;
}
```
这段代码中,我们定义了一个Graph类,用于表示无向图。在构建图时,使用add_edge方法添加节点之间的边,并记录距离和路费。
接着,使用Dijkstra算法计算最短路径。我们使用了一个distances unordered_map来记录每个节点到起点的距离,初始时将所有节点的距离设为无穷大。然后,我们使用一个优先队列(即priority_queue)来存储未标记的节点,并按照距离起点的距离进行排序。每次选择未标记的节点中距离起点最近的一个节点作为下一个计算的节点,并更新与该节点相邻的节点的最短距离。我们还使用了一个paths unordered_map来记录每个节点的前驱节点,以便在计算路径时使用。注意,在更新节点的距离和路费时,需要同时进行更新,以便得到最优的路线规划。
最后,输出起点到终点的最短距离和路线即可。
注意:这里的实现并没有考虑输入数据的合法性和异常情况,需要根据具体情况进行完善。