用c++设计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。 实现以下功能: (1)设计校园平面图,在校园景点选10个左右景点。以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等有关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条最短路径。 要求:有合理提示;根据提示,可以完成相关的功能要求
时间: 2024-02-27 14:56:05 浏览: 22
这是一个典型的图论问题,可以使用Dijkstra算法或者Floyd算法来解决。以下是实现过程的示例代码:
景点类:
```c++
class Spot {
public:
string name; // 景点名称
int id; // 景点代号
string intro; // 景点简介
Spot(string _name, int _id, string _intro) : name(_name), id(_id), intro(_intro) {}
};
```
边类:
```c++
class Edge {
public:
int from; // 起点
int to; // 终点
int dist; // 距离
Edge(int _from, int _to, int _dist) : from(_from), to(_to), dist(_dist) {}
};
```
图类:
```c++
const int MAXN = 100; // 最大节点数
const int INF = 0x3f3f3f3f; // 无穷大
class Graph {
public:
vector<Spot> spots; // 存储所有景点
vector<Edge> edges; // 存储所有边
int G[MAXN][MAXN]; // 邻接矩阵
int n; // 节点数
int m; // 边数
int d[MAXN]; // 存储最短距离
int p[MAXN]; // 存储最短路径上的前驱节点
void addSpot(Spot s) {
spots.push_back(s);
n = spots.size();
}
void addEdge(Edge e) {
edges.push_back(e);
m = edges.size();
G[e.from][e.to] = e.dist;
}
void init() {
memset(G, INF, sizeof(G));
memset(d, INF, sizeof(d));
memset(p, -1, sizeof(p));
}
void dijkstra(int s) {
bool vis[MAXN] = {false};
d[s] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
int MIN = INF;
for (int j = 0; j < n; j++) {
if (!vis[j] && d[j] < MIN) {
u = j;
MIN = d[j];
}
}
if (u == -1) {
return;
}
vis[u] = true;
for (int v = 0; v < n; v++) {
if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
d[v] = d[u] + G[u][v];
p[v] = u;
}
}
}
}
void printPath(int s, int v) {
if (v == s) {
cout << spots[s].name;
return;
}
printPath(s, p[v]);
cout << " -> " << spots[v].name;
}
Graph() {
init();
}
};
```
使用示例:
```c++
int main() {
Graph g;
g.addSpot(Spot("教学楼A", 0, "这里是教学楼A"));
g.addSpot(Spot("教学楼B", 1, "这里是教学楼B"));
g.addSpot(Spot("教学楼C", 2, "这里是教学楼C"));
g.addSpot(Spot("图书馆", 3, "这里是图书馆"));
g.addSpot(Spot("体育馆", 4, "这里是体育馆"));
g.addSpot(Spot("食堂", 5, "这里是食堂"));
g.addSpot(Spot("宿舍楼A", 6, "这里是宿舍楼A"));
g.addSpot(Spot("宿舍楼B", 7, "这里是宿舍楼B"));
g.addSpot(Spot("宿舍楼C", 8, "这里是宿舍楼C"));
g.addEdge(Edge(0, 1, 100));
g.addEdge(Edge(0, 2, 200));
g.addEdge(Edge(1, 2, 50));
g.addEdge(Edge(1, 3, 150));
g.addEdge(Edge(1, 5, 120));
g.addEdge(Edge(2, 3, 100));
g.addEdge(Edge(2, 5, 80));
g.addEdge(Edge(3, 4, 200));
g.addEdge(Edge(5, 6, 150));
g.addEdge(Edge(5, 7, 180));
g.addEdge(Edge(6, 8, 100));
g.addEdge(Edge(7, 8, 120));
int x, y;
cout << "请输入起点和终点的代号:";
cin >> x >> y;
g.dijkstra(x);
cout << "从" << g.spots[x].name << "到" << g.spots[y].name << "的最短路径长度为:" << g.d[y] << endl;
cout << "最短路径为:";
g.printPath(x, y);
cout << endl;
return 0;
}
```
用户界面可以在上述代码基础上添加交互逻辑,根据用户输入进行景点信息查询和问路查询。