Write me python code to implement dijkstras algorithm
- User
Write me python code to implement dijkstras algorithm
- Assistant
Certainly! Here's a Python code implementation of Dijkstra's algorithm:
import heapq def dijkstra(graph, start): distances = {vertex: float('inf') for vertex in graph} distances[start] = 0 queue = [(0, start)] while queue: current_distance, current_vertex = heapq.heappop(queue) if current_distance > distances[current_vertex]: continue for neighbor, weight in graph[current_vertex].items(): distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(queue, (distance, neighbor)) return distances # Example graph 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} } start_vertex = 'A' distances = dijkstra(graph, start_vertex) print("Shortest distances from vertex", start_vertex + ":") for vertex, distance in distances.items(): print("To vertex", vertex + ":", distance)In this code, the
dijkstrafunction takes in a graph (represented as a dictionary of dictionaries) and a start vertex. It initializes the distances to all vertices as infinity, except for the start vertex which is set to 0. It uses a priority queue (implemented using heapq) to keep track of the vertices to visit next, based on their distances. It repeatedly pops the vertex with the smallest distance from the queue, updates the distances of its neighbors if a shorter path is found, and adds them to the queue. Finally, it returns the shortest distances from the start vertex to all other vertices.Hope this helps!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.