用C++
时间: 2023-07-11 18:17:51 浏览: 52
好的,C++实现最短路径可以使用STL库中的优先队列和map数据结构,下面是一个C++代码示例,实现地图导航的功能,具体步骤详见代码注释:
```c++
#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <vector>
using namespace std;
// 定义地图,包括点名,路径和路径权重
map<string, map<string, int>> graph = {
{"A", {{"B", 10}, {"D", 5}}},
{"B", {{"A", 10}, {"C", 5}, {"D", 3}}},
{"C", {{"B", 5}, {"D", 8}}},
{"D", {{"A", 5}, {"B", 3}, {"C", 8}, {"E", 2}}},
{"E", {{"D", 2}}}
};
// 定义比较函数
struct cmp {
bool operator () (pair<string, int> a, pair<string, int> b) {
return a.second > b.second;
}
};
// Dijkstra算法实现
pair<int, vector<string>> shortest_path(map<string, map<string, int>> graph, string start, string end) {
// 初始化距离为无穷大
map<string, int> distances;
for (auto& node : graph) {
distances[node.first] = INT_MAX;
}
// 起点距离为0
distances[start] = 0;
// 记录最短路径
map<string, string> path;
// 已访问的节点
set<string> visited;
// 当前节点为起点
string current = start;
// 使用优先队列来实现贪心策略
priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;
pq.push(make_pair(start, 0));
while (!pq.empty()) {
// 取出距离最小的节点
pair<string, int> node = pq.top();
pq.pop();
// 如果节点已访问,则跳过
if (visited.count(node.first)) {
continue;
}
// 遍历邻居节点
for (auto& neighbor : graph[node.first]) {
// 计算到当前节点的距离
int new_distance = distances[node.first] + neighbor.second;
// 如果新距离小于原距离,则更新距离和路径
if (new_distance < distances[neighbor.first]) {
distances[neighbor.first] = new_distance;
path[neighbor.first] = node.first;
pq.push(make_pair(neighbor.first, new_distance));
}
}
// 标记当前节点为已访问
visited.insert(node.first);
}
// 生成最短路径
vector<string> shortest_path;
string current_node = end;
while (current_node != start) {
shortest_path.insert(shortest_path.begin(), current_node);
current_node = path[current_node];
}
shortest_path.insert(shortest_path.begin(), start);
// 返回最短距离和最短路径
return make_pair(distances[end], shortest_path);
}
// 主函数
int main() {
// 输入起点和终点
string start, end;
cout << "请输入起点:";
cin >> start;
cout << "请输入终点:";
cin >> end;
// 计算最短距离和最短路径
auto result = shortest_path(graph, start, end);
// 输出结果
cout << "最短距离为:" << result.first << endl;
cout << "最短路径为:";
for (auto& node : result.second) {
cout << node << " -> ";
}
cout << endl;
return 0;
}
```
在上面的代码示例中,我们定义了一个简单的地图,包括5个点A、B、C、D、E,然后使用Dijkstra算法计算最短距离和最短路径。用户可以自行输入起点和终点,程序会自动输出最短距离和最短路径。