以图中顶点 表示学校内各景点,存放景点的名称、景点介绍信息等;以边表示路 径,存放路径长度信息。要求将这些信息保存在文件graph.txt中, 系统执行时所处理的数据要对此文件分别进行读写操作。 1.从文件graph.txt中读取相应数据, 创建一个图,使用邻接矩阵表示图; 2.景点信息查询:为来访客人提供校园任意景点相关信息的介绍; 3.问路查询:为来访客人提供校园任意两个景点之间的一条最短路径代码
时间: 2024-03-17 22:44:32 浏览: 104
设计学校的校园平面图,所含景点不小于5个。以图中的顶点表示学校的各个景点,存放景点名称,代号,简介等信息;以边表示路径,存放路径,存放路径的长度等相关信息
5星 · 资源好评率100%
好的,以下是Python实现代码,其中包含了类的定义以及对应的方法实现:
```python
class CampusMap:
def __init__(self, filename):
# 读取文件,创建邻接矩阵和景点介绍字典
self.adj_matrix = []
self.info_dict = {}
with open(filename, 'r') as f:
lines = f.readlines()
n = int(lines[0])
# 初始化邻接矩阵为全0矩阵
self.adj_matrix = [[float('inf')] * n for _ in range(n)]
for i in range(1, n+1):
name, info = lines[i].strip().split(',')
self.info_dict[name] = info
for i in range(n+1, len(lines)):
a, b, w = map(int, lines[i].strip().split(','))
self.adj_matrix[a][b] = w
self.adj_matrix[b][a] = w
def get_info(self, name):
# 返回景点介绍信息
return self.info_dict.get(name, 'Not Found')
def find_shortest_path(self, start, end):
# 使用Dijkstra算法计算最短路径
n = len(self.adj_matrix)
dist = [float('inf')] * n
prev = [-1] * n
visited = set()
dist[start] = 0
while len(visited) < n:
u = min((set(range(n)) - visited), key=dist.__getitem__)
visited.add(u)
for v in range(n):
if self.adj_matrix[u][v] != float('inf') and v not in visited:
alt = dist[u] + self.adj_matrix[u][v]
if alt < dist[v]:
dist[v] = alt
prev[v] = u
path = []
u = end
while prev[u] != -1:
path.insert(0, u)
u = prev[u]
path.insert(0, u)
return path
```
以下是一个简单的测试程序,可以通过输入数字来选择不同的功能:
```python
if __name__ == '__main__':
cm = CampusMap('graph.txt')
while True:
print('请选择要执行的功能:')
print('1. 查询景点介绍')
print('2. 查询最短路径')
print('3. 退出')
choice = input()
if choice == '1':
name = input('请输入要查询的景点名称:')
info = cm.get_info(name)
print(info)
elif choice == '2':
start = input('请输入起点名称:')
end = input('请输入终点名称:')
start_idx = list(cm.info_dict.keys()).index(start)
end_idx = list(cm.info_dict.keys()).index(end)
path = cm.find_shortest_path(start_idx, end_idx)
print('最短路径为:', ' -> '.join([list(cm.info_dict.keys())[i] for i in path]))
elif choice == '3':
break
else:
print('请输入正确的选项!')
```
阅读全文