Dijkstra 算法或 Floyd 算法

Dijkstra算法和Floyd算法都是图论中常用的最短路径算法，但它们的实现方式和适用场景略有不同。

Dijkstra算法适用于有向图或者无向图中没有负权边的情况下，用于求解单源最短路径问题。该算法的基本思想是从起点开始，逐步扩展到其他节点，每次选择当前距离起点最近的一个节点进行扩展，直到扩展到终点或者无法扩展为止。Dijkstra算法的时间复杂度为O(n^2)，其中n为节点数。

以下是Dijkstra算法的Python实现代码：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典和堆
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    
    while heap:
        # 弹出堆中距离起点最近的节点
        (curr_dist, curr_node) = heapq.heappop(heap)
        
        # 如果当前节点已经被处理过，则跳过
        if curr_dist > dist[curr_node]:
            continue
        
        # 遍历当前节点的邻居节点
        for neighbor, weight in graph[curr_node].items():
            # 计算从起点到邻居节点的距离
            new_dist = dist[curr_node] + weight
            
            # 如果新的距离比之前的距离更短，则更新距离字典和堆
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return dist

Floyd算法适用于有向图或者无向图中存在负权边的情况下，用于求解任意两点之间的最短路径问题。该算法的基本思想是动态规划，通过中间节点的枚举，逐步更新每对节点之间的最短路径。Floyd算法的时间复杂度为O(n^3)，其中n为节点数。

以下是Floyd算法的Python实现代码：

def floyd(graph):
    # 初始化距离矩阵
    dist = [[float('inf') if i != j else 0 for j in range(len(graph))] for i in range(len(graph))]
    
    # 遍历图中的边，更新距离矩阵
    for i in range(len(graph)):
        for j in range(len(graph)):
            if graph[i][j] != 0:
                dist[i][j] = graph[i][j]
    
    # 枚举中间节点，更新距离矩阵
    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist