最短路径加权图python

在加权图中，最短路径指的是从一个起点到一个终点的路径上，边权值之和最小的路径。常用的最短路径算法有Dijkstra算法和Bellman-Ford算法，这里我演示一下Dijkstra算法的python实现。

假设我们有一个加权无向图，使用邻接矩阵表示，其中0表示两点之间没有边相连。

graph = [[0, 10, 0, 30, 100],
         [10, 0, 50, 0, 0],
         [0, 50, 0, 20, 10],
         [30, 0, 20, 0, 60],
         [100, 0, 10, 60, 0]]

我们希望找到从点0到点4的最短路径。

def dijkstra(graph, start, end):
    # 初始化距离数组
    n = len(graph)
    distance = [float('inf')] * n
    distance[start] = 0

    # 初始化已访问数组
    visited = [False] * n

    # 循环遍历所有节点
    for i in range(n):
        # 找到当前未访问节点中距离最近的节点
        min_distance = float('inf')
        min_index = -1
        for j in range(n):
            if not visited[j] and distance[j] < min_distance:
                min_distance = distance[j]
                min_index = j

        # 标记该节点为已访问
        visited[min_index] = True

        # 更新与该节点相邻节点的距离
        for k in range(n):
            if not visited[k] and graph[min_index][k] > 0:
                new_distance = distance[min_index] + graph[min_index][k]
                if new_distance < distance[k]:
                    distance[k] = new_distance

    # 返回起点到终点的最短距离
    return distance[end]

# 查找0到4的最短路径
print(dijkstra(graph, 0, 4))

输出结果为90，表示从点0到点4的最短路径长度为90。