最短路径算法

最短路径算法用于在图中找到两点之间的最短路径。

Dijkstra 算法

概述

Dijkstra 算法用于计算从起点到其他所有节点的最短路径，适用于非负权边的图。

实现

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    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].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# 示例图
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'A': 4, 'C': 1, 'D': 5},
    'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
    'D': {'B': 5, 'C': 8, 'E': 2, 'F': 6},
    'E': {'C': 10, 'D': 2, 'F': 3},
    'F': {'D': 6, 'E': 3}
}

print("Dijkstra 最短路径:", dijkstra(graph, 'A'))

Bellman-Ford 算法

概述

Bellman-Ford 算法可以处理带有负权边的图，并能检测负权环。

实现

def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # 松弛操作
    for _ in range(len(graph) - 1):
        updated = False
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight
                    updated = True
        if not updated:
            break
    
    # 检测负权环
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                raise ValueError("图中存在负权环")
    
    return distances

# 示例
print("Bellman-Ford 最短路径:", bellman_ford(graph, 'A'))

Floyd-Warshall 算法

概述

Floyd-Warshall 算法用于计算图中所有节点对之间的最短路径。

实现

def floyd_warshall(graph):
    nodes = list(graph.keys())
    n = len(nodes)
    
    # 初始化距离矩阵
    dist = {i: {j: float('inf') for j in nodes} for i in nodes}
    
    # 设置对角线为0
    for node in nodes:
        dist[node][node] = 0
    
    # 设置边的权重
    for node in graph:
        for neighbor, weight in graph[node].items():
            dist[node][neighbor] = weight
    
    # 动态规划更新
    for k in nodes:
        for i in nodes:
            for j in nodes:
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

# 示例
print("Floyd-Warshall 所有最短路径:", floyd_warshall(graph))

复杂度分析

算法	时间复杂度	空间复杂度	适用场景
Dijkstra	O((V+E)logV)	O(V)	非负权边
Bellman-Ford	O(VE)	O(V)	含负权边
Floyd-Warshall	O(V³)	O(V²)	所有节点对

应用场景

• 地图导航系统
• 网络路由算法
• 社交网络分析