Code an implementation of Dijkstra's algorithm in python, with comments. It will operate…
- User
Code an implementation of Dijkstra's algorithm in python, with comments. It will operate on a list of nodes represented by integers 0 to n, and an arbitrary number of connections between nodes contained in a list (connections are instances of a class, with a beginning node, end node and length).
- Assistant
Here is an implementation of Dijkstra's algorithm in Python:
class Connection: def __init__(self, start, end, length): self.start = start self.end = end self.length = length class Graph: def __init__(self, nodes): self.nodes = nodes self.adjacency_list = {node: [] for node in nodes} def add_connection(self, connection): start = connection.start end = connection.end length = connection.length self.adjacency_list[start].append((end, length)) self.adjacency_list[end].append((start, length)) def dijkstras_algorithm(graph, start): # Initialize the set of visited nodes and distance to each node visited = set() distances = {node: float("inf") for node in graph.nodes} distances[start] = 0 # Keep track of the previous node for each node previous = {node: None for node in graph.nodes} # Loop until all nodes have been visited while visited != set(graph.nodes): # Find the unvisited node with the lowest distance min_distance = float("inf") min_node = None for node in graph.nodes: if node not in visited and distances[node] < min_distance: min_distance = distances[node] min_node = node # Mark the min node as visited visited.add(min_node) # Update the distance to adjacent nodes for neighbor, length in graph.adjacency_list[min_node]: if distances[neighbor] > distances[min_node] + length: distances[neighbor] = distances[min_node] + length previous[neighbor] = min_node # Return the distance to each node and the previous node for path reconstruction return distances, previousIn this implementation, the connections are represented by a Connection class, which has start and end nodes and a length. The Graph class represents the graph, with an adjacency list that maps each node to a list of its neighboring nodes and the length of the connection between them.
The dijkstras_algorithm function takes a Graph object and a starting node as input and returns the distance to each node in the graph and the previous node for path reconstruction. It initializes a set of visited nodes, a dictionary of distances to each node, and a dictionary of previous nodes. It then iterates over the graph until all nodes have been visited, finding the unvisited node with the lowest distance and updating the distance to adjacent nodes.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.