• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

espanhol

[How To] Algoritmo de Dinic ou Dinitz

9 mensagens neste tópico

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

qual é a utilidade desse algoritmo / para que serve ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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 :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora