mixtral-8x7b-instruct-v0.1· Mistral AI Arena Human Preference 55K
Write me python code to implement dijkstras algorithm
- User
Write me python code to implement dijkstras algorithm
- Assistant
Sure, here's a Python implementation of Dijkstra's algorithm that finds the shortest path between two nodes in a weighted graph:
import heapq def dijkstra(graph, start, end): # Initialize the distance dictionary with infinite distances for all nodes except the start node distances = {node: float('infinity') for node in graph} distances[start] = 0 # Create a priority queue and add the start node with distance 0 priority_queue = [(0, start)] while priority_queue: # Get the node with the smallest distance from the priority queue current_distance, current_node = heapq.heappop(priority_queue) # If we've already visited this node with a smaller distance, skip it if current_distance > distances[current_node]: continue # Update the distances to neighboring nodes for neighbor, weight in graph[current_node].items(): distance = current_distance + weight # If we found a shorter path to the neighbor, update its distance and add it to the priority queue if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(priority_queue, (distance, neighbor)) return distances[end] # Example usage: graph = { 'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, 'C': {'A': 4, 'B': 2, 'D': 1}, 'D': {'B': 5, 'C': 1} } print(dijkstra(graph, 'A', 'D')) # Output: 3In this implementation,
graphis a dictionary where the keys are the nodes and the values are dictionaries that map neighboring nodes to their edge weights. Thedijkstrafunction returns the shortest distance between thestartandendnodes.Note that this implementation assumes that all edge weights are non-negative. If there are negative edge weights, Dijkstra's algorithm may
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.