# Define a matrix to represent distances between nodes
matrix = {
    "A": {"A": 0, "B": 7, "C": 9, "D": None, "E": None, "F": 14},
    "B": {"A": 7, "B": 0, "C": 10, "D": 15, "E": None, "F": None},
    "C": {"A": 9, "B": 10, "C": 0, "D": 11, "E": None, "F": 2},
    "D": {"A": None, "B": 15, "C": 11, "D": 0, "E": 6, "F": None},
    "E": {"A": None, "B": None, "C": None, "D": 6, "E": 0, "F": 9},
    "F": {"A": 14, "B": None, "C": 2, "D": None, "E": 9, "F": 0}
}

def dijkstra(matrix, source):
    # Get the distances from the source node to all other nodes
    start_vertex = matrix[source]
    print(start_vertex)
    
    # Initialize distances from the source to all nodes
    # If there is no direct path, set the distance to infinity
    distances = {node: start_vertex[node] if start_vertex[node] is not None else float('inf') for node in matrix}
    
    # List to keep track of visited nodes
    visited_nodes = [source]

    # Variable to keep track of the number of iterations
    iteration = 0

    # Loop until all nodes have been visited
    while len(visited_nodes) < len(matrix):
        print("\n")
        iteration += 1
        print("Iteration: ", iteration)
        print("Visited nodes: ", visited_nodes)
        print("Distances: ", distances)

        # Initialize the minimum distance to infinity
        min_distance = float("inf")
        min_vertex = None

        # Get the list of potential nodes to visit next
        potential_nodes = [node for node in distances if distances[node] != None and node not in visited_nodes]
        print("potential nodes:", potential_nodes)
        
        # Find the node with the smallest distance
        for node in range(len(potential_nodes)):
            if distances[potential_nodes[node]] < min_distance:
                min_distance = distances[potential_nodes[node]]
                min_vertex = potential_nodes[node]
        
        print("min_vertex: ", min_vertex)
        
        visited_nodes.append(min_vertex)
        neighbours = [node for node in matrix[min_vertex] if matrix[min_vertex][node] != None and node not in visited_nodes]
        
        print("neighbours: ", neighbours)
        
        for node in neighbours:
            print("node:", node, matrix[min_vertex][node])
            if distances[node] > distances[min_vertex] + matrix[min_vertex][node]:
                distances[node] = distances[min_vertex] + matrix[min_vertex][node]

    return distances
        
print(dijkstra(matrix, "A"))