图论Dijkstra Algorithm在2D空间平面网格节点图选择最短路径，networkx，Python

转x33g5p2x  于2021-12-02 转载在 Go  
字(4.6k)|赞(0)|评价(0)|浏览(511)

图论Dijkstra Algorithm在2D空间平面网格节点图选择最短路径，networkx，Python

（1）Dijkstra Algorithm算法结束后，在代码生成的二维网格图中所有节点的权值即为出发点（源点）到当前节点的最短路径。本例中网格图中所有邻接边权值为1。

（2）通过每个节点中保存的parent指针一路逆行往上迭代查找，直到出发点（源点），即为出发点到当前节点的最短路径。parent指针指向了到当前节点的最短路径父节点。

（3）Dijkstra Algorithm寻路结束后，出发点（源点）到所有可达点的最短距离确定（weight值即为最短路径值）。从中可以得到启发，比如多人对战游戏，一张地图中同一时刻多人需要知道到达某汇聚点的路径，那么这种算法应用场景，Dijkstra Algorithm就很适合（反而A算法在这种应用场景不适合，因为A算法确定的是一个出发点到一个终点的路线。如果是N个人，就需要N次运行A*算法，才能为N个人完成选路），而Dijkstra Algorithm只需一次寻路，就完成所有地图中的点（某个点代表某个人的位置）到某个源点的最短距离。

（4）Dijkstra Algorithm在本例中作为一种广度优先搜索寻找最短路径，在每个节点中加入的parent指针，将其形成一定程度具有深度的寻路思想。这种思想在寻路算法中很普遍，在广度和深度的搜索过程中，通过埋入一个指针parent，可以快速找到出发点到源点的最短路径。

  1. import random
  3. import networkx as nx
  4. import matplotlib.pyplot as plt
  6. WALKABLE = 'walkable'
  7. PARENT = 'parent'
  8. WEIGHT = 'weight'
  10. def my_graph():
  11.     M = 7
  12.     N = 9
  13.     G = nx.grid_2d_graph(m=M, n=N)
  14.     pos = nx.spring_layout(G, iterations=100)
  16.     nx.draw_networkx(G, pos=pos,
  17.                      # labels=labels, #labels = dict(((i, j), 'Phil') for i, j in G.nodes())
  18.                      font_size=8,
  19.                      font_color='white',
  20.                      node_color='green',
  21.                      node_size=500,
  22.                      width=1)
  24.     START = (1, 1)
  25.     GOAL = (M - 1 - 1, N - 1 - 1)
  27.     # 0,随机生成障碍物点
  28.     # 1,精心挑选的障碍物构成陷阱
  29.     OBSTACLE_MODE = 0
  30.     road_closed_nodes = []
  32.     if OBSTACLE_MODE == 0:
  33.         obstacle_number = 20  # 障碍物（断点、不可达点）数量
  34.         road_closed_nodes = obstacle_nodes(G, START, GOAL, obstacle_number, M, N)
  35.     elif OBSTACLE_MODE == 1:
  36.         road_closed_nodes = dummy_nodes(G)
  38.     nx.draw_networkx_nodes(
  39.         G, pos,
  40.         nodelist=road_closed_nodes,
  41.         node_size=500,
  42.         node_color="red",
  43.         node_shape="x",
  44.         # alpha=0.3,
  45.         label='x'
  46.     )
  48.     dijkstra_find_path(G, START, G.number_of_nodes() - len(road_closed_nodes))
  49.     print('G.nodes(data=True) 更新节点权值后', G.nodes(data=True))
  50.     path = find_path_by_parent(G, START, GOAL)
  51.     print('path', path)
  53.     nx.draw_networkx_nodes(
  54.         G, pos,
  55.         nodelist=path,
  56.         node_size=400,
  57.         node_color="red",
  58.         node_shape='o',
  59.         # alpha=0.3,
  60.         # label='NO'
  61.     )
  63.     path_edges = []
  64.     for i in range(len(path)):
  65.         if (i + 1) == len(path):
  66.             break
  67.         path_edges.append((path[i], path[i + 1]))
  69.     print('path_edges', path_edges)
  70.     # 把path着色加粗重新描边
  71.     nx.draw_networkx_edges(G, pos,
  72.                            edgelist=path_edges,
  73.                            width=8,
  74.                            alpha=0.5,
  75.                            edge_color="r")
  77.     plt.axis('off')
  78.     plt.show()
  80. def dijkstra_find_path(G, START, valid_node_number):
  81.     # 设置所有节点的权值为无穷大
  82.     for n in G.nodes():
  83.         G.nodes[n][WEIGHT] = float('inf')
  85.     # 更新出发节点权重为0
  86.     G.nodes[START][WEIGHT] = 0
  88.     print('G.nodes(data=True)', G.nodes(data=True))
  90.     print('起点', START)
  91.     close_list = []
  93.     vertex = START  # 顶点
  94.     while True:
  95.         print('-----')
  97.         if len(close_list) == valid_node_number:
  98.             print('搜索完毕')
  99.             break
  101.         update_weight_from_node(G, vertex, close_list)
  102.         min_node = find_min_nodes(G, vertex, close_list)
  104.         vertex = min_node[0]
  105.         close_list.append(vertex)
  107. def update_weight_from_node(G, cur_node, close_list):
  108.     cur_node_weight = G.nodes[cur_node][WEIGHT]
  109.     neighbors = nx.neighbors(G, cur_node)
  110.     for child in neighbors:
  111.         try:
  112.             walkable = G.nodes[child][WALKABLE]
  113.         except:
  114.             walkable = True
  116.         if (child in close_list) or (not walkable):
  117.             continue
  119.         edge_weight = 1  # 在本例的2D平面图中，邻接的边权都是1
  120.         child_node_weight = G.nodes[child][WEIGHT]
  121.         sum_weight = cur_node_weight + edge_weight
  122.         if sum_weight < child_node_weight:
  123.             G.nodes[child][WEIGHT] = sum_weight
  124.             G.nodes[child][PARENT] = cur_node
  125.             print('更新节点权值', cur_node, '->', child, '新权值为:', sum_weight)
  127. def find_min_nodes(G, vertex, close_list):
  128.     node_list = []
  129.     for node in G.nodes(data=True):
  130.         try:
  131.             walkable = node[1][WALKABLE]
  132.         except:
  133.             walkable = True
  135.         if walkable and (node[0] not in close_list) and (node[0] != vertex):
  136.             node_list.append(node)
  138.     min_node = min(node_list, key=lambda x: x[1][WEIGHT])
  139.     print(vertex, '最小节点', min_node)
  141.     return min_node
  143. def find_path_by_parent(G, START, GOAL):
  144.     t = GOAL
  145.     path = [t]
  146.     is_find = False
  147.     while not is_find:
  148.         for n in G.nodes(data=True):
  149.             if n[0] == t:
  150.                 parent = n[1][PARENT]
  151.                 path.append(parent)
  153.                 if parent == START:
  154.                     is_find = True
  155.                     break
  157.                 t = parent
  159.     list.reverse(path)
  160.     return path
  162. # 障碍物点
  163. def obstacle_nodes(G, START, GOAL, obstacle, M, N):
  164.     road_closed_nodes = []
  165.     for i in range(obstacle):
  166.         n = (random.randint(0, M - 1), random.randint(0, N - 1))
  167.         if n == START or n == GOAL:
  168.             continue
  169.         if n in road_closed_nodes:
  170.             continue
  172.         G.nodes[n][WALKABLE] = False
  173.         road_closed_nodes.append(n)
  175.     return road_closed_nodes
  177. def dummy_nodes(G):
  178.     fun_nodes = []
  180.     n0 = (1, 2)
  181.     G.nodes[n0][WALKABLE] = False
  182.     fun_nodes.append(n0)
  184.     n1 = (1, 3)
  185.     G.nodes[n1][WALKABLE] = False
  186.     fun_nodes.append(n1)
  187.     n2 = (1, 4)
  188.     G.nodes[n2][WALKABLE] = False
  189.     fun_nodes.append(n2)
  190.     n3 = (1, 5)
  191.     G.nodes[n3][WALKABLE] = False
  192.     fun_nodes.append(n3)
  193.     n4 = (1, 6)
  194.     G.nodes[n4][WALKABLE] = False
  195.     fun_nodes.append(n4)
  196.     n5 = (2, 6)
  197.     G.nodes[n5][WALKABLE] = False
  198.     fun_nodes.append(n5)
  199.     n6 = (3, 6)
  200.     G.nodes[n6][WALKABLE] = False
  201.     fun_nodes.append(n6)
  202.     n7 = (4, 6)
  203.     G.nodes[n7][WALKABLE] = False
  204.     fun_nodes.append(n7)
  205.     n8 = (5, 6)
  206.     G.nodes[n8][WALKABLE] = False
  207.     fun_nodes.append(n8)
  208.     n9 = (5, 5)
  209.     G.nodes[n9][WALKABLE] = False
  210.     fun_nodes.append(n9)
  211.     n10 = (5, 4)
  212.     G.nodes[n10][WALKABLE] = False
  213.     fun_nodes.append(n10)
  214.     n11 = (5, 3)
  215.     G.nodes[n11][WALKABLE] = False
  216.     fun_nodes.append(n11)
  217.     n12 = (5, 2)
  218.     G.nodes[n12][WALKABLE] = False
  219.     fun_nodes.append(n12)
  221.     return fun_nodes
  223. if __name__ == '__main__':
  224.     my_graph()

运行几轮后的选路截图：

当把障碍物模式切换为1，即特意挑选一批点围成一个围墙，同时把出发点改为(2,2)，看看算法的表现：

算法聪明的规避了围墙，没有跳进凹形陷阱。 

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/zhangphil/article/details/121274102

内容来源于网络，如有侵权，请联系作者删除！

python算法

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com