Skip to content

Latest commit

 

History

History

Redes

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

Fluxo em Redes

Algoritmos relacionados a Fluxos em Redes, baseados nas aulas do curso Algoritmos em Grafos (MAC0328).

Fluxo Máximo

Considere um digrafo com capacidades nos arcos e um par de vértices s e t. Um fluxo de s a t é um valor positivo atribuído a cada arco do digrafo menor ou igual à sua capacidade tal que a quantidade de fluxo que entra em cada vértice seja igual à quantidade que sai, exceto nos vértices s e t. O valor de um fluxo de s a t é a quantidade de fluxo que sai de s. O problema consiste em calcular um fluxo de s a t com valor máximo. Como solução, foram implementadas duas diferentes versões do algoritmo de Ford-Fulkerson, uma utilizando caminhos aumentadores mínimos e filas, e a outra utilizando caminhos aumentadores de máxima capacidade e filas de prioridade.