Skip to content
The Chat Archive
gemini-pro-dev-api· Google Arena Human Preference 55K

Code an implementation of Dijkstra's algorithm in python, with comments. It will operate…

  1. 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).

  2. Assistant
    # Node class represents a node in the graph
    class Node:
        def __init__(self, id):
            self.id = id
            self.connections = []
            self.visited = False
            self.distance = float('inf')
    
    # Connection class represents a connection between two nodes
    class Connection:
        def __init__(self, start_node, end_node, length):
            self.start_node = start_node
            self.end_node = end_node
            self.length = length
    
    # Dijkstra's algorithm implementation
    def dijkstra(start_node, nodes, connections):
        # Initialize distances and set start node distance to 0
        for node in nodes:
            node.distance = float('inf')
        start_node.distance = 0
    
        # While there are unvisited nodes
        while not all(node.visited for node in nodes):
            # Find the unvisited node with the smallest distance
            current_node = min(node for node in nodes if not node.visited)
            current_node.visited = True
    
            # Update distances of neighboring nodes
            for connection in connections:
                if connection.start_node == current_node:
                    neighbor = connection.end_node
                    if neighbor.distance > current_node.distance + connection.length:
                        neighbor.distance = current_node.distance + connection.length
    
    # Example usage
    nodes = [Node(i) for i in range(5)]
    connections = [
        Connection(nodes[0], nodes[1], 1),
        Connection(nodes[0], nodes[2], 4),
        Connection(nodes[1], nodes[2], 2),
        Connection(nodes[1], nodes[3], 6),
        Connection(nodes[2], nodes[3], 3),
        Connection(nodes[2], nodes[4], 5),
        Connection(nodes[3], nodes[4], 7),
    ]
    
    # Run Dijkstra's algorithm
    dijkstra(nodes[0], nodes, connections)
    
    # Print distances from the start node to all other nodes
    for node in nodes:
        print(f"Distance from start node to node {node.id}: {node.distance}")
    

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