Skip to content
The Chat Archive
mixtral-8x7b-instruct-v0.1· Mistral AI Arena Human Preference 55K

Write me python code to implement dijkstras algorithm

  1. User

    Write me python code to implement dijkstras algorithm

  2. 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: 3
    

    In this implementation, graph is a dictionary where the keys are the nodes and the values are dictionaries that map neighboring nodes to their edge weights. The dijkstra function returns the shortest distance between the start and end nodes.

    Note that this implementation assumes that all edge weights are non-negative. If there are negative edge weights, Dijkstra's algorithm may

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.