当前位置：首页 > article >正文

PyCharm专项训练5 最短路径算法

article 2025/1/5 3:56:22

一、实验目的

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

二、实验内容

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

三、实验演示

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

#Dijkstra：

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    priority_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]:
            continue

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances, previous_nodes

def 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}")