I had a flash during my sleep. Why would AddEdge have the possibility to add a single Node? That seems to break the Single Responsibility Principle. To fix this problem, I added an AddNode method, which initializes an empty collection for the _map's Node. The AddEdge method then calls AddNode on both the nodes of the new Edge.

public IWeightedGraphBuilder AddNode(Node node)
{
    if (node == null) throw new ArgumentNullException(nameof(node));

    _map.InitializeKeyCollection(node);

    return this;
}
    
public IWeightedGraphBuilder AddEdge(Node nodeA, Node nodeB, int weight)
{
    if (nodeA == null) throw new ArgumentNullException(nameof(nodeA));
    if (nodeB == null) throw new ArgumentNullException(nameof(nodeB));

    AddNode(nodeA);
    AddNode(nodeB);

    //The rest is the same
}

This way, the AddEdge method cannot add a single node like it's done in the previous implementation.

Was I so naive in 2015! I had a flash during my sleep. Why would AddEdge have the possibility to add a single Node? That seems to break the Single Responsibility Principle. To fix this problem, I added an AddNode method, which initializes an empty collection for the _map's Node. The AddEdge method then calls AddNode on both the nodes of the new Edge.

public IWeightedGraphBuilder AddNode(Node node)
{
    if (node == null) throw new ArgumentNullException(nameof(node));

    _map.InitializeKeyCollection(node);

    return this;
}
    
public IWeightedGraphBuilder AddEdge(Node nodeA, Node nodeB, int weight)
{
    if (nodeA == null) throw new ArgumentNullException(nameof(nodeA));
    if (nodeB == null) throw new ArgumentNullException(nameof(nodeB));

    AddNode(nodeA);
    AddNode(nodeB);

    //The rest is the same
}

This way, the AddEdge method cannot add a single node like it's done in the previous implementation, this keeps this method's responsibility count to one.