“É um ótimo algoritmo”, disse Erik Demainecientista da computação do Instituto de Tecnologia de Massachusetts. “É muito rápido, simples e fácil de implementar.”
Para colocar esse procedimento em prática, você precisaria decidir sobre um sistema para organizar suas anotações – uma estrutura de dados, no jargão da ciência da computação. Isso pode parecer um pequeno detalhe técnico, mas o tempo gasto pesquisando suas anotações sempre que você precisar editar ou remover uma entrada pode ter um grande efeito no tempo de execução geral do algoritmo.
O artigo de Dijkstra usou uma estrutura de dados simples que deixou espaço para melhorias. Nas décadas seguintes, os pesquisadores desenvolveram outros melhores, carinhosamente apelidados de “montes”, nos quais certos itens são mais fáceis de encontrar do que outros. Eles aproveitam o fato de que o algoritmo de Dijkstra só precisa remover a entrada do vértice restante mais próximo. “Um heap é basicamente uma estrutura de dados que permite fazer isso muito rapidamente”, disse Václav Rozhoňpesquisador do Instituto de Ciência da Computação, Inteligência Synthetic e Tecnologia (INSAIT) em Sófia, Bulgária.
Em 1984, dois cientistas da computação desenvolveram um design de pilha inteligente isso permitiu ao algoritmo de Dijkstra atingir um limite teórico, ou “limite inferior”, no tempo necessário para resolver o problema dos caminhos mais curtos de fonte única. Num sentido específico, esta versão do algoritmo de Dijkstra é a melhor possível. Essa foi a última palavra sobre a versão padrão do problema durante quase 40 anos. As coisas só mudaram quando alguns pesquisadores analisaram mais de perto o que significa ser “o melhor”.
Melhor Comportamento
Os pesquisadores normalmente comparam algoritmos estudando como eles se comportam nos piores cenários. Think about a rede viária mais confusa do mundo e, em seguida, adicione alguns padrões de tráfego especialmente desconcertantes. Se insistirmos em encontrar as rotas mais rápidas nestas circunstâncias extremas, a versão de 1984 do algoritmo de Dijkstra é comprovadamente imbatível.
Mas, felizmente, sua cidade não tem a pior rede viária do mundo. E então você pode perguntar: existe um algoritmo imbatível em todas as redes rodoviárias? O primeiro passo para responder a esta questão é assumir a suposição conservadora de que cada rede tem padrões de tráfego de pior caso. Então você deseja que seu algoritmo encontre os caminhos mais rápidos em qualquer format de gráfico possível, assumindo os piores pesos possíveis. Os pesquisadores chamam essa condição de “otimalidade common”. Se você tivesse um algoritmo universalmente supreme para o problema mais simples de simplesmente ir de um ponto a outro em um gráfico, ele poderia ajudá-lo a vencer o trânsito na hora do rush em todas as cidades do mundo.
