我尝试在堆栈溢出中查找我的问题的答案。我找到了这些答案，但他们的解决方案并不真正适用于我的情况，因为我有非定向边缘。我无法创建一个新的顶点，边在 Vin 处进入，边在 Vout 处退出，因为在特定方向上没有“进入”或“退出”。
（我找不到第二个堆栈问题，但答案相同）
最初的问题
我的问题是我有一个图，其中节点具有容量，所有边都是双向的，我需要找到所有路径，使我能够最大化 N 个元素在图中的流动。
基本上，它是一个 lem-in，房间容量为 1 和无限容量的双向边缘。
想象一个迷宫，你可以在隧道里容纳尽可能多的人，但每个房间只有一个人。他们可以在一个回合内从一个房间移动到另一个房间。我怎样才能做到这一点，以便人们从迷宫的开始到结束的所有方式，而不会有两个人在同一个房间里。
Edmonds-Karp 的实现
我已经设法使用邻接矩阵（它是一个使用位检查是否存在连接的整数的一维数组）实现了 Edmonds-Karp（可能非常糟糕）。
我有 3 个函数，一个运行算法本身的函数（我正在稍微简化代码，例如删除对 malloc、frees 等的保护……以便算法看起来更好）：
- 主算法循环
这是主循环。我试图找到一条增广路径。如果我不这样做，这意味着最终房间的（接收器）父级将是初始值（-1）。否则我应用路径，打印路径并继续。
void edmonds_karp(t_map *map)
{
t_deque *deque;
uint32_t *flow;
int64_t *path;
t_way *way;
flow = ft_memalloc(sizeof(uint32_t) * map->size_rooms);
while (TRUE)
{
deque = ft_deque_create();
find_augmenting_path(deque, map, &flow, &path);
if (path[get_end_room(map)->id] == -1)
break ;
apply_augmenting_path(map, &flow, path);
way = build_way_from_path(path, map);
print_way(way);
ft_deque_delete(deque);
}
}
- 找到增广路径
然后有一个函数可以找到增广路径。我只是使用带有队列的 BFS，弹出父级然后检查所有子级。如果一个孩子有一个前向连接并且仍然有容量，我将它添加到路径中，将其标记为已访问并将其推送到队列中。如果一个孩子有一个反向连接并流过它，我将它添加到路径中，将其标记为已访问并将其推送到队列中。
static int64_t find_augmenting_path(t_deque *deque, t_map *map, uint32_t **flow, int64_t **path)
{
uint32_t child_id;
uint8_t *visited;
t_room *parent;
t_room *child;
visited = ft_memalloc(sizeof(uint8_t) * map->size_rooms);
ft_deque_push_back(deque, get_start_room(map));
*path = init_path(map->size_rooms);
while (deque->head)
{
parent = ft_deque_pop_front(deque);
child_id = 0;
while (child_id < map->size_rooms)
{
if (!visited[child_id] && !map->rooms[child_id]->visited)
if ((((map->adj_matrix[parent->id] & (1ULL << child_id)) && !((*flow)[parent->id] & (1ULL << child_id))) // There is a forward connection and we still have capacity
|| ((map->adj_matrix[child_id] & (1ULL << parent->id)) && ((*flow)[child_id] & (1ULL << parent->id))))) // There is a backward connection and we have reverse capacity
{
child = get_room_by_id(map, child_id);
visited[child_id] = TRUE;
(*path)[child_id] = parent->id;
ft_deque_push_back(deque, (void*)child);
if (child->type == END)
return (SUCCESS);
}
++child_id;
}
}
return (ERROR);
}
- 应用增广路径
应用增广路径的函数非常简单，在我的例子中，所有边的容量都是 1。我们只是从终点（sink）返回，直到我们使用路径中保存的 ID 到达起点（点击）。对于每个房间，我们填充了从父母到孩子的容量和从孩子到父母的空闲容量。
static void apply_augmenting_path(t_map *map, uint32_t **flow, int64_t *path)
{
t_room *start;
t_room *parent;
t_room *child;
start = get_start_room(map);
child = get_end_room(map);
while (child->id != start->id)
{
parent = get_room_by_id(map, path[child->id]);
(*flow)[parent->id] |= 1ULL << child->id;
(*flow)[child->id] |= 0ULL << parent->id;
child = parent;
}
}
我在以下情况下添加了一张支票：
if (!visited[child_id] && !map->rooms[child_id]->visited)
此检查!map->rooms[child_id]->visited)是我在从找到的路径构建方式时添加的已访问标志。它使我可以避免在某些情况下多次占用同一个房间。
如果我有多个边缘进入，在 Edmond-Karps 中，流量将受到边缘的限制。这意味着如果我有 4 条边到一个节点，我可以有 2 个元素进入，只要我有 2 条其他边让元素出去。这种检查避免了这种情况。
但是，这是我的主要问题，通过这样做，我阻止了一些可能通过迷宫的路径。
下面的图片将向您展示问题所在。没有我的额外检查，Edmonds-Karp 运行良好，但使用边缘来找到最佳流程：
这是我添加支票以避免两次使用同一个房间时的解决方案：
这是我想找到的：
有没有办法修改我的 Edmonds-Karp 实现以获得我想要的？如果没有，我可以使用其他算法吗？
非常感谢大家的耐心等待！
PS：我没有足够的声誉，无法嵌入图片:'(