Dijkstra: custom distnce computations

[akrzemi1]

Here is a use case for the Dijkstra's algorithm. In my graph, the edges represent some physical connections between locations, and weights of the edges represent the throughput of the corresponding connection. A throughput of a path in the graph is the throughput of the tightest edge in the path. Now I want to use dijkstra_shortest_distances to find a throughput of paths between seed and all the other locations.

So, I would have to use std::greater for compare, and std::min as combine. But I would also need the algorithm to be changed. Rather than using:

• a fixed zero (for setting distances[seed]) and
• a fixed infinity (for setting initial distances),

I would need these two values -- worst possible distance and best possible distance -- to be also parameters in this algorithm.

Another observation is that while there are valid alternative compare and combine, I cannot change them individually: {compare, combine, worst-distance, best-distance} is a quadruplet that need to travel together. "worst-sistance" is not a property of typ Distance, but is dependent on compare and combine.

Maybe a helper structure would be needed:

template <std::copyable Dist, 
          std::copyable Weight,
          std::strict_weak_order<Dist, Dist> Better, 
          std::regular_invocable<Dist, Weight> Combine>
requires std::assignable_from<Dist, std::invoke_result_t<Combine, Dist, Weight>> &&
         std::convertible_to<std::invoke_result_t<Combine, Dist, Weight>, Dist>
struct measurement
{
    Better better;
    Combine combine;
    Dist best;
    Dist worst;
};

This quadruplet would have to be passed to the algorithm.

There algorithm would also impose a semantic requirements on the elements of this quadruplet, which we can express as a test function:

template <std::copyable Dist, 
          std::copyable Weight,
          std::strict_weak_order<Dist, Dist> Better, 
          std::regular_invocable<Dist, Weight> Combine>
void test_measurement(measurement<Dist, Better, Combine> m, Dist d1, Weight w1, Weight w2)
{
    {
        const Dist da = m.combine(d1, w1);      
        assert(m.better(da, m.worst));  // effect of any combination is better than the worst distance
        assert(!m.better(da, m.best));  // no combination can produce a result better than the best distance
        
        if (m.better(d1, m.worst))      // except for the worst distance
            assert(!m.better(da, d1));  // a combination never produces a better distance
    }
    {   // combination is associative with respect to weights
        const Dist d12 = m.combine(m.combine(d1, w1), w2);
        const Dist d21 = m.combine(m.combine(d1, w2), w1);
        assert(!m.better(d12, d21));
        assert(!m.better(d21, d12));
    }
}

[akrzemi1]

I can see that Boost.Graph indeed allows the customization of the zero distance and the infinity distance per function invocation: https://www.boost.org/doc/libs/latest/libs/graph/doc/dijkstra_shortest_paths.html.