segunda-feira, 22 de abril de 2013

O Algoritmo de Dijkstra

Já ouviu falar do algoritmo de Dijkstra?

O algoritmo de Dijkstra é famoso por resolver o problema de caminhos mínimos em um tempo bem considerável. Haviam outros algoritmos com o mesmo objetivo antes dele, e surgiram mais após ele, mas em questão de complexidade de implementação e testes com o pior caso, ele continua sendo o mais conveniente.

Mas vamos ao que interessa. Em maratonas de programação, é crucial conhecer esse algoritmo e saber implementá-lo em pouco tempo, pois, como diz Steven Halim (uma espécie de gênio, reconhecido por participações na maratona de programação), não basta "lembrar do algoritmo, mas não saber implementá-lo". Um bom maratonista conhece N algoritmos e implementa todos em uma velocidade alta, para que não haja perda de tempo com coisas simples, e sobre mais tempo para os problemas mais difíceis da maratona.
Portanto, você que diz conhecer o algoritmo, se desafie a implementá-lo em em menos de 5 minutos, e caso não consiga, pratique.

Agora, para quem não conhece, trate de estudar. Esse algoritmo cai em muitos exercícios, e sua lógica é muito peculiar, uma vez que abre um novo ponto de vista para quem o aprende.

Aqui estão alguns exercícios do site URI que envolvem o algoritmo Dijkstra:
Fácil:
http://www.urionlinejudge.com.br/judge/problems/view/1148
Médio:
http://www.urionlinejudge.com.br/judge/problems/view/1123
Difícil:
http://www.urionlinejudge.com.br/judge/problems/view/1085

Nota:
Nenhum problema vai estampar na cara que utiliza o algoritmo de Dijkstra, e raramente vai ser uma simples implementação de Dijkstra. Um bom problema vai envolver um pouco de interpretação de contexto, e pequenas modificações em como os grafos são representados e corridos. As vezes também será necessário uma modificação no próprio algoritmo de Dijkstra, como no terceiro caso.

Nota 2:
O algoritmo de Dijkstra faz a busca pelo grafo. A forma como o grafo é montado, é outra história. Nos primeiros dois exercícios citados, os grafos são montados com peculiaridades diferentes, porém o Dijkstra funciona da mesma maneira nos dois casos, uma vez que o grafo está montado.
Em relação ao terceiro exercício, o grafo fica ainda mais complexo, e acredito que uma modificação no Dijkstra se faça necessário. Não tenho certeza, pois ainda não resolvi, mas me disseram que o Dijkstra resolve, então vamos lá.

Por hoje é isso, estudem o Dijkstra, é importante, e no Google tem material sobrando.
Até mais.

Nenhum comentário:

Postar um comentário