代码我忘记到哪里抄的了,这个博客就是为了保存下代码,所以没有写出处,如果需要的话可以联系我补出处。
代码如下:
def dijkstra(graph,src): # graph:邻接矩阵,src:起点 if graph == None: return None # 顶点集合 nodes = [i for i in range(len(graph))] # 获取顶点列表,用邻接矩阵存储图 # 顶点是否被访问 visited = [] visited.append(src) # 初始化dis,是它的距离 dis = {src:0} # 原点到自身的距离为0 for i in nodes: dis[i] = graph[src][i] # 不在遍历循环里面,就是第一次赋值 path={src:{src:[]}} # 记录源节点到每个节点的路径 k=pre=src # pre:用于保存以前访问过的路径的,src:初始值,k:用于判断是否重复的 while nodes: # 只要顶点列表里面还有顶点就一直循环 temp_k = k mid_distance = float('inf') # 设置中间距离无穷大 for v in visited: # 已访问节点 for d in nodes: # 未访问节点 if graph[src][v] != float('inf') and graph[v][d] != float('inf'):# 有边 new_distance = graph[src][v]+graph[v][d] if new_distance <= mid_distance: mid_distance=new_distance graph[src][d]=new_distance # 进行距离更新 k=d pre=v if k!=src and temp_k==k: break dis[k]=mid_distance # 最短路径 # path[src][k]=[i for i in path[src][pre]] path[src][k]=[*path[src][pre]] path[src][k].append(k) visited.append(k) nodes.remove(k) # print(nodes) return dis,path if __name__ == '__main__': # 输入的有向图,有边存储的就是边的权值,无边就是float('inf'),顶点到自身就是0 graph = [ [0, 50, float('inf'), 40, 25, 10], [50, 0, 15, 20, float('inf'), 25], [float('inf'), 15, 0, 10, 20, float('inf')], [40, 20, 10, 0, 10, 25], [25, float('inf'), 20, 10, 0, 55], [10, 25, float('inf'), 25, 55, 0] ] dis,path= dijkstra(graph, 0) # 查找从源点0开始带其他节点的最短路径 print(dis) print(path)