Function SSpaths_k_minimal

src/procedures/proc_ss_paths.c:597–653

find k minimal weighted path (path can have different weight)

// find k minimal weighted path (path can have different weight)
static void SSpaths_k_minimal
(
	SingleSourceCtx *ctx
) {
	// initialize heap that contains the result where top path is the highest weight
	ctx->heap = Heap_new(path_cmp, NULL);

	// get first path
	WeightedPath p = {0};
	double max_weight = DBL_MAX;
	SSpaths_next(ctx, &p, max_weight);

	// iterate over all paths
	while (p.path != NULL && Heap_count(ctx->heap) < ctx->path_count - 1) {
		// fill the heap
		_add_path(&ctx->heap, &p);

		// get next path where path weight is <= max_weight
		SSpaths_next(ctx, &p, max_weight);
	}

	if(p.path == NULL) return;

	// fill the heap
	_add_path(&ctx->heap, &p);

	// update the max weight so we will get better paths
	WeightedPath *pp = Heap_peek(ctx->heap);
	max_weight = pp->weight;

	// get next path where path weight is <= max_weight
	SSpaths_next(ctx, &p, max_weight);

	while (p.path != NULL) {
		// if the heap is full check if the current path is better 
		// than the worst path if yes replace it
		pp = Heap_peek(ctx->heap);
		if(p.weight < pp->weight ||
			p.cost < pp->cost ||
			(p.cost == pp->cost &&
				Path_Len(p.path) < Path_Len(pp->path))) {
			Heap_poll(ctx->heap);
			Path_Free(pp->path);
			pp->path = Path_Clone(p.path);
			pp->weight = p.weight;
			pp->cost = p.cost;
			Heap_offer(&ctx->heap, pp);

			// update the max weight so we will get better paths
			pp = Heap_peek(ctx->heap);
			max_weight = pp->weight;
		}

		// get next path where path weight is <= max_weight
		SSpaths_next(ctx, &p, max_weight);
	}
}