Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #57 da revista programar. Faz já o download aqui!

espanhol

[How To] Algoritmo de Dinic ou Dinitz

Mensagens Recomendadas

espanhol    0
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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
espanhol    0
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 :)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
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  :)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
espanhol    0
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?

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


×

Aviso Sobre Cookies

Ao usar este site você aceita a nossa Política de Privacidade