Write a node-based data structure in Python and a function to find the shortest path…
- User
Write a node-based data structure in Python and a function to find the shortest path between two nodes as a list.
Assistant
Here's a Python implementation of a node-based graph data structure with a shortest path function using BFS (Breadth-First Search):
from collections import deque class Node: def __init__(self, value): self.value = value self.neighbors = [] def add_neighbor(self, node): if node not in self.neighbors: self.neighbors.append(node) def __repr__(self): return f"Node({self.value})" class Graph: def __init__(self): self.nodes = {} def add_node(self, value): if value not in self.nodes: self.nodes[value] = Node(value) return self.nodes[value] def add_edge(self, value1, value2, bidirectional=True): node1 = self.add_node(value1) node2 = self.add_node(value2) node1.add_neighbor(node2) if bidirectional: node2.add_neighbor(node1) def get_node(self, value): return self.nodes.get(value) def shortest_path(self, start_value, end_value): """Find shortest path between two nodes using BFS""" start_node = self.get_node(start_value) end_node = self.get_node(end_value) if not start_node or not end_node: return None if start_node == end_node: return [start_value] # BFS setup queue = deque([(start_node, [start_value])]) visited = {start_node} while queue: current_node, path = queue.popleft() for neighbor in current_node.neighbors: if neighbor == end_node: return path + [neighbor.value] if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, path + [neighbor.value])) return None # No path found # Example usage if __name__ == "__main__": # Create a graph g = Graph() # Add edges (creates nodes automatically) g.add_edge('A', 'B') g.add_edge('A', 'C') g.add_edge('B', 'D') g.add_edge('C', 'D') g.add_edge('D', 'E') g.add_edge('E', 'F') g.add_edge('C', 'F') # Find shortest paths print(g.shortest_path('A', 'F')) # Output: ['A', 'C', 'F'] print(g.shortest_path('B', 'F')) # Output: ['B', 'D', 'E', 'F'] or ['B', 'A', 'C', 'F'] print(g.shortest_path('A', 'A')) # Output: ['A'] print(g.shortest_path('A', 'Z')) # Output: None (node doesn't exist)For weighted graphs, you can modify the structure to use Dijkstra's algorithm:
import heapq class WeightedNode: def __init__(self, value): self.value = value self.edges = {} # {neighbor_node: weight} def add_edge(self, node, weight): self.edges[node] = weight def __repr__(self): return f"WeightedNode({self.value})" class WeightedGraph: def __init__(self): self.nodes = {} def add_node(self, value): if value not in self.nodes: self.nodes[value] = WeightedNode(value) return self.nodes[value] def add_edge(self, value1, value2, weight, bidirectional=True): node1 = self.add_node(value1) node2 = self.add_node(value2) node1.add_edge(node2, weight) if bidirectional: node2.add_edge(node1, weight) def get_node(self, value): return self.nodes.get(value) def shortest_path(self, start_value, end_value): """Find shortest path using Dijkstra's algorithm""" start_node = self.get_node(start_value) end_node = self.get_node(end_value) if not start_node or not end_node: return None # Priority queue: (distance, node, path) pq = [(0, start_node, [start_value])] visited = set() while pq: current_dist, current_node, path = heapq.heappop(pq) if current_node in visited: continue visited.add(current_node) if current_node == end_node: return path for neighbor, weight in current_node.edges.items(): if neighbor not in visited: heapq.heappush(pq, (current_dist + weight, neighbor, path + [neighbor.value])) return None # Example usage with weighted graph if __name__ == "__main__": wg = WeightedGraph() # Add weighted edges wg.add_edge('A', 'B', 4) wg.add_edge('A', 'C', 2) wg.add_edge('B', 'C', 1) wg.add_edge('B', 'D', 5) wg.add_edge('C', 'D', 8) wg.add_edge('C', 'E', 10) wg.add_edge('D', 'E', 2) print(wg.shortest_path('A', 'E')) # Output: ['A', 'B', 'D', 'E']The first implementation uses BFS for unweighted graphs and finds the shortest path in terms of number of edges. The second implementation uses Dijkstra's algorithm for weighted graphs and finds the shortest path in terms of total weight. Both return the path as a list of node values, or
Noneif no path exists.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.