Halcom 发表于 2019-10-20 12:15:17

dijkstra最短路算法

dijkstra最短路算法
给定终点src，从全部可能的起点出发，得到全部的最短路径。
def dijkstra(graph,src):
    length = len(graph)
    type_ = type(graph)
    if type_ == list:
      nodes =
    elif type_ == dict:
      nodes = graph.keys()

    visited =
    path = {src:{src:[]}}
    nodes.remove(src)
    distance_graph = {src:0}
    pre = next = src

    while nodes:
      distance = float('inf')
      for v in visited:
             for d in nodes:
                new_dist = graph + graph
                if new_dist <= distance:
                  distance = new_dist
                  next = d
                  pre = v
                  graph = new_dist


      path = ]
      path.append(next)

      distance_graph = distance

      visited.append(next)
      nodes.remove(next)

    return distance_graph, path


if __name__ == '__main__':
    graph_list = [   ,
            ,
            ,
            ,
            ,
            ]

    graph_dict = {"s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4, "s5":3},
                  "s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2, "s5":2},
                  "s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1, "s5":4},
                  "s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0,"s5":1},
                  "s5":{"s1": 3, "s2": 5, "s10": 2, "s12":4,"s5":0},
    }

    distance, path = dijkstra(graph_list, 2)
    #print distance, '\n', path
    distance, path = dijkstra(graph_dict, 's1')
    print distance, '\n', path

参考：graph_algorithm











Halcom 发表于 2019-10-20 14:20:16

# 起点starpoint，终点src
def dijkstra_st(graph, startpoint, src):
    length = len(graph)
#    type_ = type(graph)
#    if type_ == list:
#      nodes =
#    elif type_ == dict:
#      nodes = graph.keys()
    if isinstance(graph, list):
      nodes =
    elif isinstance(graph, dict):
      nodes = graph.keys()

    visited =
    path = {src:{src:[]}}
    nodes.remove(src)
    distance_graph = {src:0}
    pre = next = src

    while nodes:
      distance = float('inf')
      for v in visited:
             for d in nodes:
                new_dist = graph + graph
                if new_dist <= distance:
                  distance = new_dist
                  next = d
                  pre = v
                  graph = new_dist


      path = ]
      path.append(next)

      distance_graph = distance

      visited.append(next)
      nodes.remove(next)
#    return distance_graph, path
    dist = distance_graph
    path1 = path
    path1.reverse()
    path1.append(src)
    return dist, path1


if __name__ == '__main__':
    graph_list = [   ,
            ,
            ,
            ,
            ,
            ,
            ,
            ]
    # 从1到8节点的最短路径
    distance, path = dijkstra_st(graph_list, 0, 7)
    print('\n', '最优路径为： ', path)
    print(' 最优路径对应的最短距离为： %d' % distance, '\n')
    # 从2到8节点的最短路径
    distance, path = dijkstra_st(graph_list, 1, 7)
    print('最优路径为： ', path)
    print('最优路径对应的最短距离为： %d' % distance, '\n')
    # 从3到7节点的最短路径
    distance, path = dijkstra_st(graph_list, 2, 6)
    print('最优路径为： ', path)
    print('最优路径对应的最短距离为： %d' % distance, '\n')
    输出为：
最优路径为：
最优路径对应的最短距离为： 9

最优路径为：
最优路径对应的最短距离为： 9

最优路径为：
参考：【1】MATLAB dijkstra最短路算法


页: [1]
查看完整版本: dijkstra最短路算法