dijkstra_shortest_paths builds its queue as d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>, so the arity baked into one of the most widely used graph libraries is 4 rather than 2, and the header next to it says why: the arity has to be at least 2 and the optimal value appears to be 4 in their own and third-party experiments. The IndexInHeapMap in that type is the other half of the decision: it records each vertex's current slot, so relaxing an edge lifts that vertex in place instead of pushing a second copy. The two go together, because a wider heap only pays when the sift-ups from relaxation outnumber the sift-downs from settling, which is the shape of every Dijkstra run on a graph with more edges than vertices.