Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIHugging Face Arena Human Preference 55K

Write me python code to implement dijkstras algorithm

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Mistralmixtral-8x7b-instruct-v0.1’s answer.
  1. User

    Write me python code to implement dijkstras algorithm

  2. 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 dijkstra function 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!

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