Explicação do Algoritmo de Dijkstra

Поделиться
HTML-код
  • Опубликовано: 8 дек 2024
  • 📖 Meu curso de estruturas de dados e algoritmos: www.udemy.com/...
    📚 Livro para entender estruturas de dados e algoritmos: amzn.to/4bYu4VE

Комментарии • 44

  • @samueln.s
    @samueln.s 5 месяцев назад +39

    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
      @tlsaulo9229 4 месяца назад

      Então porque tem vários artigos falando que é mlogn?

    • @rafaelstutz8114
      @rafaelstutz8114 21 день назад

      ​@@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).

    • @victorkenji3532
      @victorkenji3532 21 день назад

      @@rafaelstutz8114não acho que é por aí nao. Vc está equivocado

    • @iamavalon
      @iamavalon 16 дней назад

      @@tlsaulo9229 O(log(m)) = O(log(n)) pois O(m) = O(n^2) e log n^2 = 2 log n

  • @andrewsjose4228
    @andrewsjose4228 5 месяцев назад +50

    meu sonho era achar algum canal brasileiro que abordasse diferentes tipos de algoritmos. Parabéns pelo trabalho bro

    • @gabrielfaria3496
      @gabrielfaria3496 5 месяцев назад

      tem vários livros sobre isso

    • @HillryesURA
      @HillryesURA 5 месяцев назад

      Tem vários vídeos de aulas de universidades gravadas durante a pandemia!

  • @paulo.alexandrino
    @paulo.alexandrino 5 месяцев назад +4

    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!

  • @guilhermedepaula8128
    @guilhermedepaula8128 5 месяцев назад +2

    Sua didática é diferenciada, parabéns pelo conteúdo de qualidade!

  • @victoriacassolo
    @victoriacassolo 5 месяцев назад +2

    seus conteúdos são muito bons, obrigada por compartilhar conosco!!

  • @rodrigothenopholo6778
    @rodrigothenopholo6778 5 месяцев назад

    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!

  • @guilhermecaique4139
    @guilhermecaique4139 3 месяца назад

    Ótimo video!
    Estava lendo o livro Entendendo Algoritmos e com algumas complicações com isso aqui. Muito esclarecedor!

  • @joaovitoralmeida8049
    @joaovitoralmeida8049 5 месяцев назад +1

    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

  • @Augustto366
    @Augustto366 5 месяцев назад

    Ótima explicação! Super didática!

  • @lucasmonstrox
    @lucasmonstrox 5 месяцев назад +1

    Sou fã e sempre serei! Voa jovem!

  • @prof.walterfolly-fundament7445
    @prof.walterfolly-fundament7445 5 месяцев назад

    Muito legal... Explanação simples e clara!

  • @arcbueno1
    @arcbueno1 5 месяцев назад +1

    Muito bom e direto, minha recomendação seria fazer mais videos puxando algoritmos mais conhecidos ou algortimos de ordenação (heapsort, mergesort, etc)

  • @joaorenan2746
    @joaorenan2746 5 месяцев назад +1

    Vídeo bem interessante. Sucesso!

  • @kanicsbrel82
    @kanicsbrel82 5 месяцев назад

    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

  • @g.z.anetti
    @g.z.anetti 5 месяцев назад +4

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

  • @VictorSantos-bq5oj
    @VictorSantos-bq5oj 5 месяцев назад

    que trabalho incrível, adorei a explicação, obrigado por existir e fazer esse video

  • @mkriiger
    @mkriiger 5 месяцев назад

    Muito interessante. Na faculdade não vi nem menção a esse algoritmo. Parabéns pelo conteúdo, ganhou um inscrito

  • @luscamolulo6173
    @luscamolulo6173 5 месяцев назад

    +1 Inscrito, didático, massudo e explicativo

  • @gustavoalcantara848
    @gustavoalcantara848 5 месяцев назад

    Muito bacana as always, Augusto. Quando possível, explique o algoritmo do Caixeiro Viajante

  • @embriagadodesabedoria
    @embriagadodesabedoria 5 месяцев назад

    muito bommmmm!!! teu canal é muito necessário!

  • @RO0t_32
    @RO0t_32 5 месяцев назад

    Q da hora cria uma playlist só com algoritmos aí fica bem mais fácil de ver tudo de uma vez

  • @welitonsernajotto
    @welitonsernajotto 5 месяцев назад +1

    Braboo, parabéns

  • @renemartinsbr
    @renemartinsbr 5 месяцев назад

    Mano, esse mano é daora demais!

  • @aleffelperibeirovilalba
    @aleffelperibeirovilalba 5 месяцев назад

    Pelo assunto acadêmico de algoritmo me inscrevi pelo acompanha, tópico específico seu Canal lógico

  • @cassiofiuza6833
    @cassiofiuza6833 5 месяцев назад

    Muito bom! Vlw guerreiro.

  • @vuittonprod
    @vuittonprod 5 месяцев назад +1

    Cacete, parece demais com a Sephirot arvore da vida da cabala

  • @KayanCriptografia
    @KayanCriptografia 5 месяцев назад

    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!

  • @yamsol1911
    @yamsol1911 5 месяцев назад

    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?

  • @leftyhero147
    @leftyhero147 5 месяцев назад

    Eu aprendi essa bagaça pra fazer a prova de AED e depois deletei do cérebro. Bom vídeo.

  • @feavenmundo
    @feavenmundo 5 месяцев назад

    bom dia galego te amo obrigado pelo conteudo

  • @preguica_net
    @preguica_net 5 месяцев назад

    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

  • @gilklebermedeiros4629
    @gilklebermedeiros4629 5 месяцев назад

    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?

    • @rafaelstutz8114
      @rafaelstutz8114 21 день назад

      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.

  • @MuriloTonelloBadim
    @MuriloTonelloBadim 2 месяца назад +1

    que programa o senhor esta usando caba? toca de falar pro padrinho né

  • @paulohenriquesilveira5257
    @paulohenriquesilveira5257 5 месяцев назад

    Good!

  • @guimaraesalysson
    @guimaraesalysson 5 месяцев назад

    Comecei a assistir pra saber o que era e na vdd já sabia. É simplesmente otimização matemática 😮