Gratidão pelo vídeo! só uma correção: dijkstra é: O(n^2+m) ou O(m*log2 m), ependendo de sua implementação, respectivamente, para grafos densos e grafos esparsos sendo N a quantidade de vértices e M a de arestas
@@tlsaulo9229 Se sua implementação usar heap binária, vc vai precisar inicializar e atualizar ela. Inicializar custa O(n), atualizar custa O(log n). Podemos simplificar a análise do dijkstra em duas partes: A extração do nó com menor distância (1) e a atualização das distâncias (2). A primeira parte vai custar O(n * log n), pq vc precisa extrair o nó da heap e essa extração pode ser feita até n vezes - uma pra cada vértice. Cada extração custa O(log n), pq extrair da heap significa remover o elemento mínimo e reorganizar a estrutura dela. A segunda etapa também custa O(log n) pra cada operação. A atualização das distâncias é feita para cada aresta, resultando em O(m * log n). No final, somando as duas etapas, vc fica com O((n+m) * log n).
Minha dissertação foi sobre economia dos transportes e eu penei para entender minimamente o funcionamento da biblioteca que usei para estimar tempos de deslocamento entre n pontos através de uma rede de ônibus. Sua explicação teria facilitado demais. Excelente vídeo!
Vídeo sensacional! Comecei a ler ontem o livro Arquitetura Limpa, e logo no começo o uncle bob menciona Dijkstra e seu algoritmo, não tinha ficado muito claro, para eu, como funcionava esse algoritmo, mas com esse vídeo abriu minha mente! Muito obrigado!
Você é foda, traz um vídeo sobre lock otimista, pessimista e database constraints, quando usar cada um, trade-offs com o objetivo de resolver problemas de concorrência
Muito bom e direto, minha recomendação seria fazer mais videos puxando algoritmos mais conhecidos ou algortimos de ordenação (heapsort, mergesort, etc)
brasil ta precisando de gente assim, por favor, quando tiver grandao seu canal nao deixe de fazer videos em portugues :) tem mt gente q ta começando no ingles tbm
Muito legal seu canal, mano! São poucos canais que trazem um conteúdo mais acadêmico sobre programação... Os que estão em altam só falam sobre programação web, full stack, etc. Curso bacharelado em Matemática e produzo vídeos com um viés acadêmico (matemático) sobre Segurança da Informação, mais especificamente Criptografia. Agradeço se der uma olhada!
Olá Augusto. Gostaria de te parabenizar pelo vídeo, uma forma bem prática de entender o algoritmo! Se for possível, gostaria de saber qual software você utiliza em seus vídeos. Seria o Excalidraw?
Cara, uma coisa que eu ainda não entendi sobre o algoritmo de dijkstra é que parece que existem duas implementações. Uma, como a do vídeo, onde ele simplesmente itera sobre todos os vértices e outra onde o algoritmo vai sempre passando pelo menor caminho, tipo, se o caminho A pra B é menor que o caminho de A pra C, então o algoritmo vai seguir aquele caminho. Alguém pode me explicar melhor? qual a melhor implementação?
Tem duas formas clássicas de implementar o algoritmo de Dijkstra: a primeira é uma versão simples que itera por todos os vértices a cada passo para encontrar o nó com a menor distância atual, fazendo uma busca linear. A segunda utiliza uma heap (fila de prioridade) pra armazenar os vértices e acessar diretamente o nó com a menor distância, "seguindo o menor caminho" em vez de iterar por todos os vértices. Geralmente, a versão com heap é melhor, pq tem complexidade O((n+m)logn) e é muito mais rápida pra grafos grandes. A primeira versão tem complexidade O(n^2 + m), pode ser melhor pra grafos pequenos ou densos.
Gratidão pelo vídeo! só uma correção: dijkstra é: O(n^2+m) ou O(m*log2 m), ependendo de sua implementação, respectivamente, para grafos densos e grafos esparsos
sendo N a quantidade de vértices e M a de arestas
Então porque tem vários artigos falando que é mlogn?
@@tlsaulo9229 Se sua implementação usar heap binária, vc vai precisar inicializar e atualizar ela. Inicializar custa O(n), atualizar custa O(log n). Podemos simplificar a análise do dijkstra em duas partes: A extração do nó com menor distância (1) e a atualização das distâncias (2). A primeira parte vai custar O(n * log n), pq vc precisa extrair o nó da heap e essa extração pode ser feita até n vezes - uma pra cada vértice. Cada extração custa O(log n), pq extrair da heap significa remover o elemento mínimo e reorganizar a estrutura dela. A segunda etapa também custa O(log n) pra cada operação. A atualização das distâncias é feita para cada aresta, resultando em O(m * log n). No final, somando as duas etapas, vc fica com O((n+m) * log n).
@@rafaelstutz8114não acho que é por aí nao. Vc está equivocado
@@tlsaulo9229 O(log(m)) = O(log(n)) pois O(m) = O(n^2) e log n^2 = 2 log n
meu sonho era achar algum canal brasileiro que abordasse diferentes tipos de algoritmos. Parabéns pelo trabalho bro
tem vários livros sobre isso
Tem vários vídeos de aulas de universidades gravadas durante a pandemia!
Minha dissertação foi sobre economia dos transportes e eu penei para entender minimamente o funcionamento da biblioteca que usei para estimar tempos de deslocamento entre n pontos através de uma rede de ônibus. Sua explicação teria facilitado demais. Excelente vídeo!
Sua didática é diferenciada, parabéns pelo conteúdo de qualidade!
seus conteúdos são muito bons, obrigada por compartilhar conosco!!
Vídeo sensacional! Comecei a ler ontem o livro Arquitetura Limpa, e logo no começo o uncle bob menciona Dijkstra e seu algoritmo, não tinha ficado muito claro, para eu, como funcionava esse algoritmo, mas com esse vídeo abriu minha mente! Muito obrigado!
Ótimo video!
Estava lendo o livro Entendendo Algoritmos e com algumas complicações com isso aqui. Muito esclarecedor!
Você é foda, traz um vídeo sobre lock otimista, pessimista e database constraints, quando usar cada um, trade-offs com o objetivo de resolver problemas de concorrência
Sou fã e sempre serei! Voa jovem!
Ótima explicação! Super didática!
Muito bom e direto, minha recomendação seria fazer mais videos puxando algoritmos mais conhecidos ou algortimos de ordenação (heapsort, mergesort, etc)
up
Muito legal... Explanação simples e clara!
Opa, estava lendo livro sobre isso essa semana, mas uma informação importante: Ele não resolve em O(n) mas sim O(n log n).
brasil ta precisando de gente assim, por favor, quando tiver grandao seu canal nao deixe de fazer videos em portugues :) tem mt gente q ta começando no ingles tbm
Muito interessante. Na faculdade não vi nem menção a esse algoritmo. Parabéns pelo conteúdo, ganhou um inscrito
Vídeo bem interessante. Sucesso!
que trabalho incrível, adorei a explicação, obrigado por existir e fazer esse video
muito bommmmm!!! teu canal é muito necessário!
+1 Inscrito, didático, massudo e explicativo
Muito bacana as always, Augusto. Quando possível, explique o algoritmo do Caixeiro Viajante
Cacete, parece demais com a Sephirot arvore da vida da cabala
Braboo, parabéns
Pelo assunto acadêmico de algoritmo me inscrevi pelo acompanha, tópico específico seu Canal lógico
Mano, esse mano é daora demais!
Q da hora cria uma playlist só com algoritmos aí fica bem mais fácil de ver tudo de uma vez
Muito legal seu canal, mano! São poucos canais que trazem um conteúdo mais acadêmico sobre programação... Os que estão em altam só falam sobre programação web, full stack, etc. Curso bacharelado em Matemática e produzo vídeos com um viés acadêmico (matemático) sobre Segurança da Informação, mais especificamente Criptografia. Agradeço se der uma olhada!
Muito bom! Vlw guerreiro.
Olá Augusto. Gostaria de te parabenizar pelo vídeo, uma forma bem prática de entender o algoritmo!
Se for possível, gostaria de saber qual software você utiliza em seus vídeos. Seria o Excalidraw?
Eu aprendi essa bagaça pra fazer a prova de AED e depois deletei do cérebro. Bom vídeo.
bom dia galego te amo obrigado pelo conteudo
que programa o senhor esta usando caba? toca de falar pro padrinho né
Q jeito
A didática da ciências da computação não é muito boa, eles estão mais preocupados em cobrar do que ensinar, mas com você foi tranquilo. Valeu
Cara, uma coisa que eu ainda não entendi sobre o algoritmo de dijkstra é que parece que existem duas implementações. Uma, como a do vídeo, onde ele simplesmente itera sobre todos os vértices e outra onde o algoritmo vai sempre passando pelo menor caminho, tipo, se o caminho A pra B é menor que o caminho de A pra C, então o algoritmo vai seguir aquele caminho. Alguém pode me explicar melhor? qual a melhor implementação?
Tem duas formas clássicas de implementar o algoritmo de Dijkstra: a primeira é uma versão simples que itera por todos os vértices a cada passo para encontrar o nó com a menor distância atual, fazendo uma busca linear. A segunda utiliza uma heap (fila de prioridade) pra armazenar os vértices e acessar diretamente o nó com a menor distância, "seguindo o menor caminho" em vez de iterar por todos os vértices. Geralmente, a versão com heap é melhor, pq tem complexidade O((n+m)logn) e é muito mais rápida pra grafos grandes. A primeira versão tem complexidade O(n^2 + m), pode ser melhor pra grafos pequenos ou densos.
Good!
Comecei a assistir pra saber o que era e na vdd já sabia. É simplesmente otimização matemática 😮