机械加工网上接单平台_徐州百度推广_seo智能优化公司_站长工具seo综合查询关键词

一、实验目的

        本文的实验目的是通过编程实践，掌握并应用Dijkstra（迪杰斯特拉）算法和Floyd（弗洛伊德）算法来解决图论中的最短路径问题。

二、实验内容

1. 数据准备：
   • 使用邻接表的形式定义两个图graph_dijkstra和graph_floyd，图中包含节点以及节点之间的边和对应的权重。
2. 算法实现：
   • 实现Dijkstra算法，从指定的源节点（节点0）出发，计算并输出到图中其他所有节点的最短距离及路径。
   • 实现Floyd算法，计算并输出图中任意两点之间的最短距离及路径。
3. 结果输出：
   • 对于Dijkstra算法，输出从源节点（节点0）到指定目标节点（如节点4）的最短距离和路径。
   • 对于Floyd算法，输出图中任意两点（如节点0到节点4）之间的最短距离和路径，以验证算法的正确性和有效性。

三、实验演示

       1.Dijkstra算法&实验结果截图：

#Dijkstra：import heapqdef dijkstra(graph, start):distances = {node: float('infinity') for node in graph}distances[start] = 0priority_queue = [(0, start)]previous_nodes = {node: None for node in graph}while priority_queue:current_distance, current_node = heapq.heappop(priority_queue)if current_distance > distances[current_node]:continuefor neighbor, weight in graph[current_node]:distance = current_distance + weightif distance < distances[neighbor]:distances[neighbor] = distanceprevious_nodes[neighbor] = current_nodeheapq.heappush(priority_queue, (distance, neighbor))return distances, previous_nodesdef get_path(previous_nodes, start, end):path = []while end is not None:path.append(end)end = previous_nodes[end]path.reverse()return path if path and path[0] == start else []# 图的表示（邻接表）
graph_dijkstra = {0: [(1,4), (7, 8)],1: [(0, 4), (7, 11), (2, 8)],2: [(1, 8), (8, 2), (3, 7),(5,4)],3: [(2,7 ), (5, 14), (4, 9)],4: [(3, 9),(5,10)],5: [(2,4),(3,14),(4,10),(6,2)],6: [(5,2),(7,1),(8,6)],7: [(0,8),(1,4),(6,1),(8,7)],8: [(2,2),(6,6),(7,7)]
}start_node = 0
end_node = 4
distances, previous_nodes = dijkstra(graph_dijkstra, start_node)print(f"从节点 {start_node} 到节点 {end_node} 的最短距离: {distances[end_node]}")
path = get_path(previous_nodes, start_node, end_node)
print(f"从节点 {start_node} 到节点 {end_node} 的最短路径: {path}")

        2.Floyd算法&实验结果截图：

#Floyd
import heapq  
def floyd_warshall(graph):  num_nodes = len(graph)  distances = [[float('inf')] * num_nodes for _ in range(num_nodes)]  previous_nodes = [[-1] * num_nodes for _ in range(num_nodes)]  for u in graph:  for v, weight in graph[u]:  distances[u][v] = weight  previous_nodes[u][v] = u  distances[v][u] = weight  # 对于无向图  previous_nodes[v][u] = v  for i in range(num_nodes):  distances[i][i] = 0  for k in range(num_nodes):  for i in range(num_nodes):  for j in range(num_nodes):  if distances[i][j] > distances[i][k] + distances[k][j]:  distances[i][j] = distances[i][k] + distances[k][j]  previous_nodes[i][j] = previous_nodes[k][j]  return distances, previous_nodes  def reconstruct_path(previous_nodes, start, end):  path = []  while end != -1:  path.append(end)  end = previous_nodes[start][end]  path.reverse()  return path if path and path[0] == start else []   # 图的表示（邻接表）  
graph_floyd = {  0: [(1,4), (7, 8)],  1: [(0, 4), (7, 11), (2, 8)],  2: [(1, 8), (8, 2), (3, 7),(5,4)],  3: [(2,7 ), (5, 14), (4, 9)],  4: [(3, 9),(5,10)],5: [(2,4),(3,14),(4,10),(6,2)],6: [(5,2),(7,1),(8,6)],7: [(0,8),(1,4),(6,1),(8,7)],8: [(2,2),(6,6),(7,7)]
}  distances_floyd, previous_nodes_floyd = floyd_warshall(graph_floyd)  
start_node = 0  
end_node = 4  print(f"\n从节点 {start_node} 到节点 {end_node} 的最短距离: {distances_floyd[start_node][end_node]}")  
path = reconstruct_path(previous_nodes_floyd, start_node, end_node)  
print(f"从节点 {start_node} 到节点 {end_node} 的最短路径: {path}")