Estou implementando esse algoritmo para um gráfico direcionado. Mas o interessante sobre os nós deste gráfico também tem suas próprias capacidades de fluxo. Eu acho que essa mudança sutil do problema original deve ser tratada de uma maneira especial. Porque, no problema de fluxo máximo original, não havia problema em encontrar um caminho do início ao fim (na verdade, no algoritmo Edmonds-Karp, precisamos fazer o BFS e escolher o primeiro caminho que atinja o nó final). Mas, com este nó, extensão de capacidade, precisamos ter mais cuidado com o trabalho 'essa seleção de caminho'. Eu sei disso porque, implementei o algoritmo original e me vi obtendo valores de fluxo menores que o fluxo máximo, duvido que isso esteja relacionado às restrições de capacidade desse nó.

Eu me esforcei bastante nisso e tive algumas idéias, como transformar o gráfico inicial em um gráfico que não tem restrição de capacidade nos nós, adicionando auto-loops (adicionando auto-loops a cada nó e encontrando caminhos que incluem esses auto-loops para cada nó no caminho) ou adicionar nós e arestas virtuais cujos pesos superam as restrições iniciais de capacidade do nó) No entanto, não estou convencido de que qualquer uma dessas seja uma boa solução para esse problema.

Qualquer idéia seria muito apreciad

Desde já, obrigado