请选择 进入手机版 | 继续访问电脑版

Hello Mat

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 724|回复: 1

dijkstra最短路算法

[复制链接]

786

主题

928

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
30078
发表于 2019-10-20 12:15:17 | 显示全部楼层 |阅读模式
dijkstra最短路算法
给定终点src,从全部可能的起点出发,得到全部的最短路径。
  1. def dijkstra(graph,src):
  2.     length = len(graph)
  3.     type_ = type(graph)
  4.     if type_ == list:
  5.         nodes = [i for i in xrange(length)]
  6.     elif type_ == dict:
  7.         nodes = graph.keys()

  8.     visited = [src]
  9.     path = {src:{src:[]}}
  10.     nodes.remove(src)
  11.     distance_graph = {src:0}
  12.     pre = next = src

  13.     while nodes:
  14.         distance = float('inf')
  15.         for v in visited:
  16.              for d in nodes:
  17.                 new_dist = graph[src][v] + graph[v][d]
  18.                 if new_dist <= distance:
  19.                     distance = new_dist
  20.                     next = d
  21.                     pre = v
  22.                     graph[src][d] = new_dist


  23.         path[src][next] = [i for i in path[src][pre]]
  24.         path[src][next].append(next)

  25.         distance_graph[next] = distance

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

  28.     return distance_graph, path


  29. if __name__ == '__main__':
  30.     graph_list = [   [0, 2, 1, 4, 5, 1],
  31.             [1, 0, 4, 2, 3, 4],
  32.             [2, 1, 0, 1, 2, 4],
  33.             [3, 5, 2, 0, 3, 3],
  34.             [2, 4, 3, 4, 0, 1],
  35.             [3, 4, 7, 3, 1, 0]]

  36.     graph_dict = {  "s1":{"s1": 0, "s2": 2, "s10": 1, "s12": 4, "s5":3},
  37.                     "s2":{"s1": 1, "s2": 0, "s10": 4, "s12": 2, "s5":2},
  38.                     "s10":{"s1": 2, "s2": 1, "s10": 0, "s12":1, "s5":4},
  39.                     "s12":{"s1": 3, "s2": 5, "s10": 2, "s12":0,"s5":1},
  40.                     "s5":{"s1": 3, "s2": 5, "s10": 2, "s12":4,"s5":0},
  41.     }

  42.     distance, path = dijkstra(graph_list, 2)
  43.     #print distance, '\n', path
  44.     distance, path = dijkstra(graph_dict, 's1')
  45.     print distance, '\n', path
复制代码


参考:[1]graph_algorithm











算法QQ  3283892722
群智能算法链接http://halcom.cn/forum.php?mod=forumdisplay&fid=73
回复

使用道具 举报

786

主题

928

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
30078
 楼主| 发表于 2019-10-20 14:20:16 | 显示全部楼层
  1. # 起点starpoint,终点src
  2. def dijkstra_st(graph, startpoint, src):
  3.     length = len(graph)
  4. #    type_ = type(graph)
  5. #    if type_ == list:
  6. #        nodes = [i for i in xrange(length)]
  7. #    elif type_ == dict:
  8. #        nodes = graph.keys()
  9.     if isinstance(graph, list):
  10.         nodes = [i for i in range(length)]
  11.     elif isinstance(graph, dict):
  12.         nodes = graph.keys()

  13.     visited = [src]
  14.     path = {src:{src:[]}}
  15.     nodes.remove(src)
  16.     distance_graph = {src:0}
  17.     pre = next = src

  18.     while nodes:
  19.         distance = float('inf')
  20.         for v in visited:
  21.              for d in nodes:
  22.                 new_dist = graph[src][v] + graph[v][d]
  23.                 if new_dist <= distance:
  24.                     distance = new_dist
  25.                     next = d
  26.                     pre = v
  27.                     graph[src][d] = new_dist


  28.         path[src][next] = [i for i in path[src][pre]]
  29.         path[src][next].append(next)

  30.         distance_graph[next] = distance

  31.         visited.append(next)
  32.         nodes.remove(next)
  33. #    return distance_graph, path
  34.     dist = distance_graph[startpoint]
  35.     path1 = path[src][startpoint]
  36.     path1.reverse()
  37.     path1.append(src)
  38.     return dist, path1


  39. if __name__ == '__main__':
  40.     graph_list = [   [0, 1, 2, 999, 7, 4, 8, 999],
  41.             [1, 0, 2, 5, 999, 999, 7, 999],
  42.             [2, 2, 0, 1, 5, 999, 999, 999],
  43.             [999, 5, 1, 0, 3, 999, 999, 6],
  44.             [7, 999, 5, 3, 0, 3, 999, 4],
  45.             [4, 999, 999, 999, 3, 0, 2, 6],
  46.             [8, 7, 999, 999, 999, 2, 0, 4],
  47.             [999, 999, 999, 6, 4, 6, 4, 0]]
  48.     # 从1到8节点的最短路径
  49.     distance, path = dijkstra_st(graph_list, 0, 7)
  50.     print('\n', '最优路径为: ', path)
  51.     print(' 最优路径对应的最短距离为: %d' % distance, '\n')
  52.     # 从2到8节点的最短路径
  53.     distance, path = dijkstra_st(graph_list, 1, 7)
  54.     print('最优路径为: ', path)
  55.     print('最优路径对应的最短距离为: %d' % distance, '\n')
  56.     # 从3到7节点的最短路径
  57.     distance, path = dijkstra_st(graph_list, 2, 6)
  58.     print('最优路径为: ', path)
  59.     print('最优路径对应的最短距离为: %d' % distance, '\n')
  60.    
复制代码
输出为:
  1. 最优路径为:  [0, 2, 3, 7]
  2. 最优路径对应的最短距离为: 9

  3. 最优路径为:  [1, 2, 3, 7]
  4. 最优路径对应的最短距离为: 9

  5. 最优路径为:  [2, 0, 5, 6]
复制代码

参考:【1】MATLAB dijkstra最短路算法


算法QQ  3283892722
群智能算法链接http://halcom.cn/forum.php?mod=forumdisplay&fid=73
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Python|Opencv|MATLAB|Halcom.cn  

GMT+8, 2020-1-25 09:35 , Processed in 0.118070 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表