Function find_optimal_path

plugins/renepay/mcf.c:1004–1079

TODO(eduardo): unit test this Similar to `find_admissible_path` but use Dijkstra to optimize the distance * label. Stops when the target is hit. */

/* Similar to `find_admissible_path` but use Dijkstra to optimize the distance
 * label. Stops when the target is hit. */
static bool find_optimal_path(const tal_t *ctx, struct dijkstra *dijkstra,
			      const struct linear_network *linear_network,
			      const struct residual_network *residual_network,
			      const u32 source, const u32 target,
			      struct arc *prev, char **fail)
{
	tal_t *this_ctx = tal(ctx,tal_t);
	bool target_found = false;

	bitmap *visited = tal_arrz(this_ctx, bitmap,
					BITMAP_NWORDS(linear_network->max_num_nodes));

	if(!visited)
	{
		if(fail)
		*fail = tal_fmt(ctx, "bad allocation of visited");
		goto finish;
	}


	for(size_t i=0;i<tal_count(prev);++i)
		prev[i].idx=INVALID_INDEX;

	const s64 *const distance=dijkstra_distance_data(dijkstra);

	dijkstra_init(dijkstra);
	dijkstra_update(dijkstra,source,0);

	while(!dijkstra_empty(dijkstra))
	{
		u32 cur = dijkstra_top(dijkstra);
		dijkstra_pop(dijkstra);

		if(bitmap_test_bit(visited,cur))
			continue;

		bitmap_set_bit(visited,cur);

		if(cur==target)
		{
			target_found = true;
			break;
		}

		for(struct arc arc = node_adjacency_begin(linear_network,cur);
		        !node_adjacency_end(arc);
			arc = node_adjacency_next(linear_network,arc))
		{
			// check if this arc is traversable
			if(residual_network->cap[arc.idx] <= 0)
				continue;

			u32 next = arc_head(linear_network,arc);

			s64 cij = residual_network->cost[arc.idx]
					- residual_network->potential[cur]
					+ residual_network->potential[next];