[How To] Algoritmo de Dinic ou Dinitz

[espanhol]

Boas, este deve ser o meu primeiro post no forum 🙂

Alguém me consegue facultar uma implementação deste algoritmo ou o seu Pseudo-Código?

Obrigado

[deathseeker25]

Boas espanhol, sê bem-vindo ao fórum. Numa pesquisa encontrei algumas coisas que te podem interessar:

http://www.mpi-sb.mpg.de/~sanders/courses/algdat03/maxflow.pdf

http://i10www.ira.uka.de/sanders/courses/algdat02/index.html

http://magma.maths.usyd.edu.au/magma/htmlhelp/text1416.htm

Espero que ajudem.

Cumps

[espanhol]

tks isso deve ajudar

[mogers]

qual é a utilidade desse algoritmo / para que serve ?

[espanhol]

Serve para calcular o fluxo máximo de um grafo, é uma evolução do edmonds-karp que assimptoticamente o tempo que demora a executar é próximo ao relabel-to-front 🙂

[edumad]

ah!... claro...  :ohwell:

[mogers]

Serve para calcular o fluxo máximo de um grafo, é uma evolução do edmonds-karp que assimptoticamente o tempo que demora a executar é próximo ao relabel-to-front 🙂

Podias explicar melhor isso? talvez dar um exercício de aplicação desses algoritmos... nunca tinha ouvido falar destes  🙂

[espanhol]

Posso, claro.

Imagina que tens um conjunto de máquinas que estão ligadas umas às outras através de passadeiras rolantes, as passadeiras são diferentes na medida em que dão para um certo número de peças, por exemplo a passadeira que liga a máquina A à máquina B tem capacidade para 10 peças, mas a que liga a máquina C à máquina F só permite 4 peças.

Imagina que querias saber qual era o número total de peças máximo (fluxo máximo) que conseguias enviar de uma Máquina I(nicial) para a Máquina F(inal) de modo a que nunca tivesses atrasos, nem passadeiras sobrecarregadas.

Deves usar um algoritmo de fluxo máximo (como o de Dinitz ou Dinic) para calcular esse total.

Got it?

[mogers]

yah 😄   thanks