Scribd
Upload
81 views

A Algorithm For Graph

This document describes an implementation of the A* search algorithm to find the shortest path between nodes in a graph. It defines a Graph class that takes an adjacency list as input and implements functions like get_neighbors() and a heuristic function h(). The a_star_algorithm() method uses queues and data structures to iteratively search the graph and reconstruct the shortest path when the target node is found. It provides an example graph and calls a_star_algorithm() to find the shortest path from node 'A' to 'H'.

Uploaded by

Brijesh Kuvadiya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
81 views

A Algorithm For Graph

This document describes an implementation of the A* search algorithm to find the shortest path between nodes in a graph. It defines a Graph class that takes an adjacency list as input and implements functions like get_neighbors() and a heuristic function h(). The a_star_algorithm() method uses queues and data structures to iteratively search the graph and reconstruct the shortest path when the target node is found. It provides an example graph and calls a_star_algorithm() to find the shortest path from node 'A' to 'H'.

Uploaded by

Brijesh Kuvadiya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

In [5]: 1 from collections import deque

2
3 class Graph:
4
5 def __init__(self, adjacency_list):
6 self.adjacency_list = adjacency_list
7
8 def get_neighbors(self, v):
9 return self.adjacency_list[v]
10
11 # heuristic function with equal values for all nodes
12 def h(self, n):
13 H = {
14 'A': 1,
15 'B': 1,
16 'C': 1,
17 'D': 1,
18 'E': 1,
19 'F': 1,
20 'G': 1,
21 'H': 1,
22 }
23
24 return H[n]
25
26 def a_star_algorithm(self, start_node, stop_node):
27
28 open_list = set([start_node])
29 closed_list = set([])
30
31 # g == current distances from start_node to all other nodes
32 g = {}
33
34 g[start_node] = 0
35
36 # parents == an adjacency map of all nodes
37 parents = {}
38 parents[start_node] = start_node
39
40 while len(open_list) > 0:
41 n = None
42
43 # find a node with the lowest value of f()
44 for v in open_list:
45 if n == None or g[v] + self.h(v) < g[n] + self.
46 n = v;
47
48 if n == None:
49 print('Path does not exist!')
50 return None
51
52 # if the current node is the stop_node
53 # then reconstruct the path from it to the start_node
54 if n == stop_node:
55 reconst_path = []
56
56
57 while parents[n] != n:
58 reconst_path.append(n)
59 n = parents[n]
60
61 reconst_path.append(start_node)
62
63 reconst_path.reverse()
64
65 print('Path found: {}'.format(reconst_path))
66 return reconst_path
67
68 # for all neighbors of the current node do
69 for (m, weight) in self.get_neighbors(n):
70 # if current node isn't in both open_list and clos
71 # add it to open_list and note n as it's parent
72 if m not in open_list and m not in closed_list:
73 open_list.add(m)
74 parents[m] = n
75 g[m] = g[n] + weight
76
77 # otherwise, check if it's quicker to first visit n
78 # and if it is, update parent data and g data
79 # and if the node was in the closed_list, move it t
80 else:
81 if g[m] > g[n] + weight:
82 g[m] = g[n] + weight
83 parents[m] = n
84
85 if m in closed_list:
86 closed_list.remove(m)
87 open_list.add(m)
88
89 # remove n from the open_list, and add it to closed_lis
90 # because all of his neighbors were inspected
91 open_list.remove(n)
92 closed_list.add(n)
93
94 print('Path does not exist!')
95 return None
96
97 graph = {
98 'A' : [('B', 8),],
99 'B' : [('A', 8),('C', 10), ('D', 12), ('E', 6)],
100 'C' : [('B',10),('E',10),('F',9) ],
101 'D' : [('B',12)],
102 'E' : [('B',6), ('C',10), ('G',70)],
103 'F' : [('C',9), ('G',7), ('H',12)],
104 'G' : [('E',70), ('F',7), ('H',15)],
105 'H' : [('F',12), ('G',15)],
106 }
107
108 graph1 = Graph(graph)
109 graph1.a_star_algorithm('A', 'H')

Path found: ['A', 'B', 'C', 'F', 'H']

Out[5]: ['A', 'B', 'C', 'F', 'H']

You might also like