Graph DijkstraAlgorithm selects shortest path in planar grid node graph in 2D space, networkx, Python-1024programmer

Graph Dijkstra Algorithm selects the shortest path in the 2D space plane grid node graph, networkx, Python

(1) After the Dijkstra Algorithm algorithm is completed, the two-dimensional code generated The weight of all nodes in the grid graph is the shortest path from the starting point (source point) to the current node. In this example, the weight of all adjacent edges in the grid graph is 1.

(2) Iteratively search all the way up through the parent pointer saved in each node, until you reach the starting point (source point), which is the shortest path from the starting point to the current node. The parent pointer points to the shortest path parent node to the current node.

(3) After the Dijkstra Algorithm pathfinding is completed, the shortest distance from the starting point (source point) to all reachable points is determined (the weight value is the shortest path value). You can get inspiration from it. For example, in a multiplayer battle game, multiple people on a map need to know the path to a certain convergence point at the same time. Then the Dijkstra Algorithm is very suitable for this algorithm application scenario (on the contrary, the Aalgorithm is very suitable for this kind of application scenario. The application scenario is not suitable because the Aalgorithm determines the route from a starting point to an end point. If there are N people, it will take N times to run the A* algorithm to complete route selection for N people), while Dijkstra Algorithm only One pathfinding is required to complete the shortest distance from all points in the map (a certain point represents the location of a certain person) to a certain source point.

(4) Dijkstra Algorithm in this example is used as a breadth-first search to find the shortest path. The parent pointer is added to each node to form a path-finding idea with a certain degree of depth. This idea is very common in pathfinding algorithms. During the search process of breadth and depth, by burying a pointer parent, the shortest path from the starting point to the source point can be quickly found.

import random import networkx as nx import matplotlib.pyplot as plt WALKABLE = 'walkable' PARENT = 'parent' WEIGHT = ' weight' def my_graph(): M = 7 N = 9 G = nx.grid_2d_graph(m=M, n=N) pos = nx.spring_layout(G, iteratiOns=100) nx.draw_networkx(G, pos=pos, # labels=labels, #labels = dict(((i, j), 'Phil') for i, j in G.nodes( )) font_size=8, font_color='white', node_color='green', node_size=500, x' ) dijkstra_find_path(G, START, G.number_of_nodes() - len(road_closed_nodes)) print('G.nodes(data=True) after updating node weights', G.nodes(data=True)) path = find_path_by_parent( G, START, GOAL) print('path', path) nx.draw_networkx_nodes( G, pos, nodelist=path, node_size=400, node_color= "red", node_shape='o', # alpha=0.3, # label='NO' ) path_edges = [] for i in range(len (path)): if (i + 1) == len(path): break path_edges.append((path[i], path[i + 1])) print ('path_edges', path_edges) # Make the path bold and re-stroke nx.draw_networkx_edges(G, pos, edgelist=path_edges, off') plt.show( ) def dijkstra_find_path(G, START, valid_node_number): # Set the weights of all nodes to infinity for n in G.nodes(): G.nodes[n][WEIGHT] = float('inf') # Update the starting node weight to 0 G.nodes[START][WEIGHT] = 0 print('G.nodes(data=True)', G.nodes (data=True)) print('Start', START) close_list = [] vertex = START # Vertex while True: print('-----' ) if len(close_list) == valid_node_number: print('Search completed') break update_weight_from_node(G, vertex, close_list) min_node = find_min_nodes(G, vertex, close_list ) vertex = min_node[0] close_list.append(vertex) def update_weight_from_node(G, cur_node, close_list): cur_node_weight = G.nodes[cur_node][WEIGHT] neighbors = nx.neighbors(G, cur_node) for child in neighbors: try: walkable = G.nodes[child][WALKABLE] except: walkable = True if (child in close_list) or (not walkable): continue edge_weight = 1 # In the 2D plane in this example, the adjacent edge weights are all 1 child_node_weight = G.nodes[child][ WEIGHT] sum_weight = cur_node_weight + edge_weight if sum_weight <child_node_weight: G.nodes[child][WEIGHT] = sum_weight G.nodes[child][PARENT] = cur_node print ('Update node weight', cur_node, '->', child, 'The new weight is:', sum_weight) def find_min_nodes(G, vertex, close_list): node_list = [] for node in G.nodes(data=True): try: walkable = node[1][WALKABLE] except: walkable = True if walkable and (node[0 ] not in close_list) and (node[0] != vertex): node_list.append(node) min_node = min(node_list, key=lambda x: x[1][WEIGHT]) print(vertex, 'minimum node', min_node) return min_node def find_path_by_parent(G, START, GOAL): t = GOAL path = [t] is_find = False while not is_find: for n in G.nodes(data=True): if n[0] == t: parent = n[1][PARENT] path.append(parent) if parent == START: is_find = True break t = parent list.reverse( path) return path # Obstacle points def obstacle_nodes(G, START, GOAL, obstacle, M, N): road_closed_nodes = [] for i in range(obstacle) : n = (random.randint(0, M - 1), random.randint(0, N - 1)) if n == START or n == GOAL: continue if n in road_closed_nodes: continue G.nodes[n][WALKABLE] = False road_closed_nodes.append(n) return road_closed_nodes def dummy_nodes(G): fun_nodes = [] n0 = (1, 2) G.nodes[n0][WALKABLE] = False fun_nodes.append(n0) n1 = (1, 3) G .nodes[n1][WALKABLE] = False fun_nodes.append(n1) n2 = (1, 4) G.nodes[n2][WALKABLE] = False fun_nodes.append( n2) n3 = (1, 5) G.nodes[n3][WALKABLE] = False fun_nodes.append(n3) n4 = (1, 6) G. nodes[n4][WALKABLE] = False fun_nodes.append(n4) n5 = (2, 6) G.nodes[n5][WALKABLE] = False fun_nodes.append(n5 ) n6 = (3, 6) G.nodes[n6][WALKABLE] = False fun_nodes.append(n6) n7 = (4, 6) G.nodes [n7][WALKABLE] = False fun_nodes.append(n7) n8 = (5, 6) G.nodes[n8][WALKABLE] = False fun_nodes.append(n8) n9 = (5, 5) G.nodes[n9][WALKABLE] = False fun_nodes.append(n9) n10 = (5, 4) G.nodes[ n10][WALKABLE] = False fun_nodes.append(n10) n11 = (5, 3) G.nodes[n11][WALKABLE] = False fun_nodes.append(n11) n12 = (5, 2) G.nodes[n12][WALKABLE] = False fun_nodes.append(n12) return fun_nodes if __name__ == '__main__': my_graph()

Screenshots of route selection after running several rounds:

Use obstacle mode Switch to 1, that is, a group of points are specially selected to form a wall, and the starting point is changed to (2,2) to see the performance of the algorithm: