Projeto e Análise de Algoritmos I

Aula 18 - Distância em Grafos Valorados: Heaps e Dijkstra Otimizado

Lucas Nunes Alegre

Universidade Federal do Rio Grande do Sul
Instituto de Informática
Departamento de Informática Teórica


Estes slides utilizam conteúdo adaptado da bibliografia da disciplina e também de notas de aula e slides prévios dos professores Bruno Grisci, Rodrigo Machado e André Grahl.

Melhorando o Algoritmo de Dijkstra

Dijkstra

What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.

— Edsger Dijkstra, in an interview with Philip L. Frana, Communications of the ACM, 2001[5]

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Escolhendo a Estrutura de Dados Certa

  • O objetivo de uma estrutura de dados é organizar a informação para que o acesso e a manipulação sejam eficientes.

Exemplos

  • Fila (Queue): usada na Busca em Largura (BFS)
    Organiza os elementos em ordem sequencial, onde inserir no final e remover no início custam \mathcal{O}(1).

  • Pilha (Stack): usada na Busca em Profundidade (DFS)
    Permite inserir e remover do topo em tempo constante \mathcal{O}(1).

A escolha da estrutura certa é metade do caminho para um bom algoritmo.

Escolhendo a Estrutura de Dados Certa



Princípio da Parcimônia

Escolha a estrutura de dados mais simples que suporte todas as operações necessárias da sua aplicação.

Caminho Mínimo com Origem Única

Problema do Caminho Mínimo com Origem Única

Entrada:

  • Um grafo direcionado G=(V,E)
    • Cada arco tem um custo não negativo l_e para e\in E.
  • Vértice de origem s.

Saída: Para cada v\in V:

  • L(v)= custo do menor caminho entre s-v em G (distância).

Importante:

  • l_e \geq 0, \forall e\in E.
  • Assumiremos representação por lista de adjacência.

Visualização do Algoritmo de Dijkstra

lucasalegre.github.io/dijkstra-visualizer

Análise do Algoritmo de Dijkstra

\begin{algorithmic} \Procedure{Dijkstra}{$G=(V,E,w), s$} \State \textbf{Entrada:} Um grafo com pesos não-negativos $(V, E, w)$ e um nodo $s \in V$ \State \textbf{Saída:} Uma tabela $\textcolor{#9e0300}{\text{dist}}$ associando cada $v \in V$ à sua distância $d(s,v)$ \State // Inicialização \State $\textcolor{#2e75b6}{X} \gets \{s\}$ \State $\textcolor{#9e0300}{\text{dist}}(s) \gets 0$ \State $\textcolor{#9e0300}{\text{dist}}(v) \gets +\infty$ para todo $v \neq s$ \State // Laço principal \While{existe uma aresta $(v, w)$ tal que $v \in \textcolor{#2e75b6}{X}$ e $w \notin \textcolor{#2e75b6}{X}$} \State $(v^*, w^*) \gets$ tal aresta que minimiza $\textcolor{#9e0300}{\text{dist}}(v) + \ell_{vw}$ \State Adicione $w^*$ a $\textcolor{#2e75b6}{X}$ \State $\textcolor{#9e0300}{\text{dist}}(w^*) \gets \textcolor{#9e0300}{\text{dist}}(v^*) + \ell_{v^*w^*}$ \EndWhile \State \textbf{Retorne} $\textcolor{#9e0300}{\text{dist}}$ \EndProcedure \end{algorithmic}

P. Qual o tempo de execução?

\mathcal{O}(mn).

Otimizando o Algoritmo de Dijkstra

  • 1959: Dijkstra publica o algoritmo em um artigo de três páginas (A note on two problems in connexion with graphs). A versão original faz uma busca linear pelo próximo vértice, sem heap: \mathcal{O}(n^2).
  • 1964: J. W. J. Williams introduz o heap binário, junto com o HeapSort.
  • Anos 1970: heaps passam a ser usados como fila de prioridade no Dijkstra (incluindo os d-heaps de Donald Johnson, 1977), reduzindo o tempo para \mathcal{O}(m \log n).

Heaps e Fila de Prioridade

P. Quais as operações que precisamos?

Operação Tempo de Execução
Inserir (Insert) \mathcal{O}(\log n)
Extrair Mínimo (ExtractMin) \mathcal{O}(\log n)
Encontrar Mínimo (FindMin) \mathcal{O}(1)
Heapificar (Heapify) \mathcal{O}(n)
Remover (Delete) \mathcal{O}(\log n)


  • A versão de Dijkstra que veremos usa apenas Insert e ExtractMin.

Também é possível implementar um heap para encontrar o maior valor de forma análoga.

O que Armazenar no Heap?

Ideia Intuitiva

Uma primeira ideia seria armazenar as arestas do grafo no heap, substituindo as buscas de mínimo por chamadas a ExtractMin.

  • Essa abordagem funciona, mas há uma versão mais simples e eficiente: armazenar os vértices.
  • Embora o score de Dijkstra seja definido para arestas, o que realmente nos importa é qual vértice será processado em seguida.
  • O heap guarda pares (d, v): o vértice v com a distância d conhecida até ele, usada como sua prioridade.
  • O heap começa apenas com (0, s). Um vértice só entra no heap quando é alcançado por uma aresta saindo de um vértice processado.
  • Um mesmo vértice pode aparecer mais de uma vez no heap, com distâncias diferentes. Só a menor importa.

Invariante Mantido pelo Heap

Invariante

Para w \in \textcolor{#6b777d}{V - X}, \textcolor{#9e0300}{\text{dist}}(w) é uma estimativa: o menor score de Dijkstra de uma aresta com início v \in \textcolor{#2e75b6}{X} e fim w, ou +\infty se nenhuma aresta assim existir. \textcolor{#9e0300}{\text{dist}}(w) = \min_{(v, w) \in E,\; v \in \textcolor{#2e75b6}{X}} \underbrace{\big\{\, \textcolor{#9e0300}{\text{dist}}(v) + \ell_{vw} \,\big\}}_{\text{score de Dijkstra}} Para v \in \textcolor{#2e75b6}{X}, \textcolor{#9e0300}{\text{dist}}(v) já é a distância final d(s, v), computada em uma iteração anterior.

Conteúdo do Heap

  • Se \textcolor{#9e0300}{\text{dist}}(w) < +\infty, o heap contém o par (\textcolor{#9e0300}{\text{dist}}(w), w).
  • O heap também pode conter pares obsoletos (d, w): com w \in \textcolor{#2e75b6}{X}, ou com d > \textcolor{#9e0300}{\text{dist}}(w).

Pares obsoletos de w \in \textcolor{#6b777d}{V - X} têm d > \textcolor{#9e0300}{\text{dist}}(w) e não saem antes do par válido de w.

Logo, o primeiro par válido extraído é o vértice de \textcolor{#6b777d}{V - X} com menor \textcolor{#9e0300}{\text{dist}}.

Invariante Mantido pelo Heap

processados ainda não processados X V − X score = 7 score = 3 score = 5 s u w z dist(u) = 3 dist(w) = 5 dist(z) = +∞
  • Um heap possível: \textcolor{#3a7a10}{H} = \{(3, u),\ (5, w),\ \textcolor{#9aa5ad}{(7, u)}\}.
  • O par (7, u) é obsoleto se foi inserido antes de descobrirmos o score 3.
  • Como \textcolor{#9e0300}{\text{dist}}(z) = +\infty, z ainda não está no heap.

Atualização da Fronteira em Dijkstra

Mudança da Fronteira

A cada iteração, um vértice u é movido de \textcolor{#6b777d}{V - X} para \textcolor{#2e75b6}{X}, alterando a fronteira:

  • Arestas de \textcolor{#2e75b6}{X} para u deixam de cruzar a fronteira.
  • Arestas de u para vértices em \textcolor{#6b777d}{V - X} passam a cruzar a fronteira.


Consequência

O invariante exige que, para cada w \in \textcolor{#6b777d}{V - X}, \textcolor{#9e0300}{\text{dist}}(w) = \min_{(v,w) \in E,\; v \in \textcolor{#2e75b6}{X}} \underbrace{\big\{\, \textcolor{#9e0300}{\text{dist}}(v) + \ell_{vw} \,\big\}}_{\text{\footnotesize score de Dijkstra}} As novas arestas que cruzam a fronteira (saindo de u) podem reduzir \textcolor{#9e0300}{\text{dist}}(w) de alguns vértices w.

Atualização da Fronteira em Dijkstra

processados ainda não processados X V − X s u w z (a) Antes processados ainda não processados X V − X s u w z (b) Depois cruzam a fronteira vértice u movido para X

Atualização das Distâncias no Heap

Quando um vértice u entra em \textcolor{#2e75b6}{X}

  • As novas arestas cruzando a fronteira partem de u.
  • Basta percorrer a lista de adjacência de u e, para cada aresta (u, v): \text{se } \textcolor{#9e0300}{\text{dist}}(u) + \ell_{uv} < \textcolor{#9e0300}{\text{dist}}(v): \quad \textcolor{#9e0300}{\text{dist}}(v) \gets \textcolor{#9e0300}{\text{dist}}(u) + \ell_{uv}
  • Se v \in \textcolor{#2e75b6}{X}, o teste sempre falha: \textcolor{#9e0300}{\text{dist}}(v) já é a menor distância possível.

Como diminuir a distância de v no heap?

  • Remover o par antigo com Delete exige saber onde v está no vetor do heap (um mapa auxiliar vértice → posição).
  • Mais simples: apenas insira o novo par (\textcolor{#9e0300}{\text{dist}}(v), v) com Insert. O par antigo de v continua no heap, mas fica obsoleto.
  • Ao extrair um par (d, u) com u \in \textcolor{#2e75b6}{X}, basta descartá-lo.

Algoritmo de Dijkstra com Fila de Prioridade

\begin{algorithmic} \Procedure{DijkstraHeap}{$G=(V,E), s, \ell$} \State \textbf{Entrada:} Grafo dirigido $G = (V, E)$ em representação por listas de adjacência, um vértice $s \in V$, e pesos $\ell_e \geq 0$ para cada $e \in E$ \State \textbf{Pós-condição:} Para todo vértice $v$, o valor $\textcolor{#9e0300}{\text{dist}}(v)$ é a distância $d(s, v)$ \State $\textcolor{#2e75b6}{X} \gets \emptyset$ \State $\textcolor{#9e0300}{\text{dist}}(v) \gets +\infty$ para todo $v \in V$ \State $\textcolor{#9e0300}{\text{dist}}(s) \gets 0$ \State $\textcolor{#3a7a10}{H} \gets$ heap contendo apenas o par $(0, s)$ \While{$\textcolor{#3a7a10}{H}$ não está vazio} \State $(d, u) \gets \text{ExtractMin}(\textcolor{#3a7a10}{H})$ \If{$u \in \textcolor{#2e75b6}{X}$} \State \textbf{continue} \Comment{par obsoleto: $u$ já foi processado} \EndIf \State Adicione $u$ a $\textcolor{#2e75b6}{X}$ \Comment{$d = \textcolor{#9e0300}{\text{dist}}(u)$} \For{cada aresta $(u, v) \in E$} \If{$d + \ell_{uv} < \textcolor{#9e0300}{\text{dist}}(v)$} \State $\textcolor{#9e0300}{\text{dist}}(v) \gets d + \ell_{uv}$ \State $\text{Insert}(\textcolor{#3a7a10}{H}, (\textcolor{#9e0300}{\text{dist}}(v), v))$ \EndIf \EndFor \EndWhile \State \textbf{Retorne} $\textcolor{#9e0300}{\text{dist}}$ \EndProcedure \end{algorithmic}

Na primeira vez que u é extraído, d = \textcolor{#9e0300}{\text{dist}}(u): cada nova inserção de u tem distância menor que as anteriores, então o par mais recente é o primeiro a sair.

Algoritmo de Dijkstra com Fila de Prioridade: Execução

1 3 5 4 4 1 2 6 S A B D C E F
ExtractMin Ação \textcolor{#3a7a10}{H} ao fim da iteração
— inicialização: \textcolor{#9e0300}{\text{dist}}(S) = 0 (0, S)
(0, S) processa S: \textcolor{#9e0300}{\text{dist}}(A) = 1, \textcolor{#9e0300}{\text{dist}}(B) = 3 (1, A),\ (3, B)
(1, A) processa A: \textcolor{#9e0300}{\text{dist}}(D) = 6, \textcolor{#9e0300}{\text{dist}}(C) = 5 (3, B),\ (5, C),\ (6, D)
(3, B) processa B: \textcolor{#9e0300}{\text{dist}}(C) = 4 (4, C),\ \textcolor{#9aa5ad}{(5, C)},\ (6, D)
(4, C) processa C: \textcolor{#9e0300}{\text{dist}}(E) = 10 \textcolor{#9aa5ad}{(5, C)},\ (6, D),\ (10, E)
\textcolor{#9aa5ad}{(5, C)} obsoleto: C \in \textcolor{#2e75b6}{X}, descarta (6, D),\ (10, E)
(6, D) processa D: \textcolor{#9e0300}{\text{dist}}(E) = 8 (8, E),\ \textcolor{#9aa5ad}{(10, E)}
(8, E) processa E: nenhuma melhora \textcolor{#9aa5ad}{(10, E)}
\textcolor{#9aa5ad}{(10, E)} obsoleto: E \in \textcolor{#2e75b6}{X}, descarta \emptyset

F nunca entra no heap: \textcolor{#9e0300}{\text{dist}}(F) = +\infty.

Custo das Operações no Heap

Observação Importante

Quase todo o trabalho na versão com heap do algoritmo de Dijkstra é feito por operações de heap (Insert e ExtractMin).

  • Cada operação custa \mathcal{O}(\log k), onde k é o número de pares no heap.


  • Um mesmo vértice pode estar no heap mais de uma vez, com distâncias diferentes.
  • A linha 15 (Insert) executa sempre que alguma distância diminui;
  • A linha 8 (ExtractMin) executa uma vez para cada par inserido, inclusive os obsoletos.

P. Quantas inserções podem acontecer no total?

Algoritmo de Dijkstra com Fila de Prioridade

\begin{algorithmic} \Procedure{DijkstraHeap}{$G=(V,E), s, \ell$} \State \textbf{Entrada:} Grafo dirigido $G = (V, E)$ em representação por listas de adjacência, um vértice $s \in V$, e pesos $\ell_e \geq 0$ para cada $e \in E$ \State \textbf{Pós-condição:} Para todo vértice $v$, o valor $\textcolor{#9e0300}{\text{dist}}(v)$ é a distância $d(s, v)$ \State $\textcolor{#2e75b6}{X} \gets \emptyset$ \State $\textcolor{#9e0300}{\text{dist}}(v) \gets +\infty$ para todo $v \in V$ \State $\textcolor{#9e0300}{\text{dist}}(s) \gets 0$ \State $\textcolor{#3a7a10}{H} \gets$ heap contendo apenas o par $(0, s)$ \While{$\textcolor{#3a7a10}{H}$ não está vazio} \State $(d, u) \gets \text{ExtractMin}(\textcolor{#3a7a10}{H})$ \If{$u \in \textcolor{#2e75b6}{X}$} \State \textbf{continue} \Comment{par obsoleto: $u$ já foi processado} \EndIf \State Adicione $u$ a $\textcolor{#2e75b6}{X}$ \Comment{$d = \textcolor{#9e0300}{\text{dist}}(u)$} \For{cada aresta $(u, v) \in E$} \If{$d + \ell_{uv} < \textcolor{#9e0300}{\text{dist}}(v)$} \State $\textcolor{#9e0300}{\text{dist}}(v) \gets d + \ell_{uv}$ \State $\text{Insert}(\textcolor{#3a7a10}{H}, (\textcolor{#9e0300}{\text{dist}}(v), v))$ \EndIf \EndFor \EndWhile \State \textbf{Retorne} $\textcolor{#9e0300}{\text{dist}}$ \EndProcedure \end{algorithmic}

Contagem de Operações e Complexidade Final

Responsabilidade por Arestas

Cada aresta (u, v) é examinada uma única vez: quando u é processado (linhas 12 a 15). Pares obsoletos são descartados sem percorrer arestas (linhas 9 e 10).

  • Cada aresta gera no máximo um Insert: no máximo m + 1 pares no heap, contando (0, s);
  • Cada par é extraído no máximo uma vez: no máximo m + 1 chamadas de ExtractMin.

Complexidade Total

\text{Operações de heap: } \mathcal{O}(m) \qquad \text{Custo por operação: } \mathcal{O}(\log m) = \mathcal{O}(\log n) \text{pois } m \le n^2 \Rightarrow \log m \le 2 \log n \Rightarrow \text{Tempo total (com a inicialização em } \mathcal{O}(n)\text{): } \boxed{\mathcal{O}((m + n)\log n)}

Mais rápido que \mathcal{O}(mn) da implementação sem heap!

Análise de Complexidade

Python 3.12.3, Ubuntu 24.04.2 LTS, Intel® Core™ i7-4810MQ × 8

Análise de Complexidade

Python 3.12.3, Ubuntu 24.04.2 LTS, Intel® Core™ i7-4810MQ × 8

Implementação em Python

Implementação em Python

Heaps

Heaps como Árvores

Conceito

Um heap pode ser visto como uma árvore binária enraizada, em que cada nó possui 0, 1 ou 2 filhos, e cada nível é preenchido o máximo possível.

Organização dos Níveis

  • Quando o número de elementos é uma unidade a menos que uma potência de 2, todos os níveis estão completos.
  • Caso contrário, apenas o último nível pode estar incompleto, preenchido da esquerda para a direita.
(a) n = 7 (b) n = 15 (c) n = 9

Heaps como Árvores

A Propriedade dos Heaps

Para cada objeto x, a chave de x é menor ou igual às chaves dos seus filhos.

4 4 8 9 4 12 9 11 13
4 4 4 9 11 13 8 12 9

Heaps como Vetores

nível 0 nível 1 nível 2 nível 3 4 4 8 9 4 12 9 11 13 H 4 1 4 2 8 3 9 4 4 5 12 6 9 7 11 8 13 9 nível 0 nível 1 nível 2 nível 3
Elemento Posição no Vetor (começando em 1)
Pai de i \lfloor i/2 \rfloor (para i \geq 2)
Filho esquerdo de i 2i (se 2i \leq n)
Filho direito de i 2i + 1 (se 2i + 1 \leq n)

Desafio: Manter o Heap Correto e Completo

O Desafio Ao inserir ou remover um elemento, é preciso:

  1. Manter a árvore completa (ou o mais cheia possível);
  2. Preservar a propriedade de heap, corrigindo violações quando surgirem.


Estratégia Geral

Mantenha a árvore cheia da forma mais óbvia e depois conserte locais que violam a propriedade de heap.

Implementando Insert

Operação Insert

Dado um heap \textcolor{#3a7a10}{H} e um novo elemento x, adicione x a \textcolor{#3a7a10}{H} respeitando essas duas regras.

  1. Adicione o novo objeto ao final do heap e aumente o tamanho do heap.
  2. Repetidamente troque o novo objeto pelo seu pai até a propriedade de heap ser restaurada.

Insert: Exemplo

4 4 8 9 4 12 9 11 13

Insert: Exemplo

4 4 8 9 4 12 9 11 13 7

Insert: Exemplo

4 4 8 9 4 12 9 11 13 7 10

Insert: Exemplo

violação! 4 4 8 9 4 12 9 11 13 7 10 5

Insert: Exemplo

violação! 4 4 8 9 4 5 9 11 13 7 10 12

Insert: Exemplo

4 4 5 9 4 8 9 11 13 7 10 12

Operações Insert e SiftUp em um Heap

\begin{algorithmic} \Procedure{Insert}{$\textcolor{#3a7a10}{H}, x$} \State \textbf{Entrada:} Heap $\textcolor{#3a7a10}{H}$ e novo elemento $x$ \State \textbf{Saída:} Heap $\textcolor{#3a7a10}{H}$ com $x$ inserido, mantendo a propriedade de heap \State Adicione $x$ ao final do vetor que representa $\textcolor{#3a7a10}{H}$ \State $\texttt{i} \gets$ posição de $x$ \State \texttt{SiftUp}($\textcolor{#3a7a10}{H}, i$) \EndProcedure \end{algorithmic}
\begin{algorithmic} \Procedure{SiftUp}{$\textcolor{#3a7a10}{H}, i$} \State \textbf{Entrada:} Heap $\textcolor{#3a7a10}{H}$ e posição $i$ de um elemento potencialmente fora de lugar \While{$i > 1$ e $\textcolor{#3a7a10}{H}[i] < \textcolor{#3a7a10}{H}[\lfloor i/2 \rfloor]$} \State Troque $\textcolor{#3a7a10}{H}[i]$ e $\textcolor{#3a7a10}{H}[\lfloor i/2 \rfloor]$ \State $i \gets \lfloor i/2 \rfloor$ \EndWhile \EndProcedure \end{algorithmic}

  • Cada troca reduz o índice pela metade, garantindo tempo total \mathcal{O}(\log n).

  • Cada troca pode empurrar a violação da propriedade de heap para cima.

    • P. Por que não para baixo?

Implementando ExtractMin

Operação ExtractMin

Dado um heap \textcolor{#3a7a10}{H}, remova e devolva de \textcolor{#3a7a10}{H} um objeto com a menor chave.

  • A raiz de um heap é sempre o elemento mínimo. Ao removê-la, precisamos restaurar as propriedades:
    • A árvore deve continuar binária completa;
    • A propriedade de heap deve ser mantida.

Estratégia

Assim como na operação Insert, seguimos o método mais direto:

  • Pegamos o último nó da árvore;
  • Colocamos seu valor na posição da raiz (substituindo o antigo mínimo);
  • Em seguida, corrigimos possíveis violações da propriedade de heap.

ExtractMin: Exemplo

mínimo último 4 4 8 9 4 12 9 11 13

ExtractMin: Exemplo

violações! 13 4 8 9 4 12 9 11

Duas violações. Qual escolher? Sempre trocar com o menor valor!

ExtractMin: Exemplo

violações! 4 13 8 9 4 12 9 11

ExtractMin: Exemplo

4 4 8 9 13 12 9 11

Operações ExtractMin e SiftDown em um Heap

\begin{algorithmic} \Procedure{ExtractMin}{$\textcolor{#3a7a10}{H}$} \State \textbf{Entrada:} Heap $\textcolor{#3a7a10}{H}$ \State \textbf{Saída:} Elemento mínimo removido e heap atualizado \State $min \gets \textcolor{#3a7a10}{H}[1]$ \Comment{a raiz contém o menor elemento} \State $\textcolor{#3a7a10}{H}[1] \gets \textcolor{#3a7a10}{H}[\text{tamanho}(\textcolor{#3a7a10}{H})]$ \State Remova o último elemento do vetor de $\textcolor{#3a7a10}{H}$ \State \texttt{SiftDown}($\textcolor{#3a7a10}{H}, 1$) \State \textbf{retorne} $min$ \EndProcedure \end{algorithmic}

Operações ExtractMin e SiftDown em um Heap

SiftDown — min-heap, índices a partir de 1:

\begin{algorithmic} \Procedure{SiftDown}{$\textcolor{#3a7a10}{H}, i$} \State $n \gets \text{tamanho}(\textcolor{#3a7a10}{H})$ \While{$2i \le n$} \State $m \gets 2i$ \Comment{filho esquerdo} \If{$m+1 \le n$ \textbf{e} $\textcolor{#3a7a10}{H}[m+1] < \textcolor{#3a7a10}{H}[m]$} \State $m \gets m+1$ \Comment{escolhe o menor filho} \EndIf \If{$\textcolor{#3a7a10}{H}[i] \le \textcolor{#3a7a10}{H}[m]$} \State \textbf{break} \EndIf \State Troque $\textcolor{#3a7a10}{H}[i]$ e $\textcolor{#3a7a10}{H}[m]$ \State $i \gets m$ \EndWhile \EndProcedure \end{algorithmic}

  • Cada troca reduz o nível da árvore, garantindo tempo total \mathcal{O}(\log n).

  • Durante o SiftDown, no máximo dois pares pai–filho violam a propriedade de heap; cada troca empurra o nó uma camada para baixo até que ele alcance o último nível (ou antes), e os demais pares permanecem válidos, garantindo término e corretude.

HeapSort

Ordenando Vetores com Heaps

\begin{algorithmic} \Procedure{SelectionSort}{$A$} \State $n \gets \text{length}(A)$ \For{$i \gets 1$ \textbf{to} $n$} \State $m \gets i$ \For{$j \gets i$ \textbf{to} $n$} \If{$A[j] < A[m]$} \State $m \gets j$ \EndIf \EndFor \State \Call{Swap}{$A, i, m$} \EndFor \EndProcedure \end{algorithmic}
\begin{algorithmic} \Procedure{Swap}{$A, x, y$} \State $tmp \gets A[x]$ \State $A[x] \gets A[y]$ \State $A[y] \gets tmp$ \EndProcedure \end{algorithmic}

Tempo: \Theta(n^2)

Ordenando Vetores com Heaps

\begin{algorithmic} \Procedure{HeapSort}{$A$} \State \textbf{Entrada:} Vetor $A$ com $n$ inteiros distintos \State \textbf{Saída:} Vetor $B$ com os mesmos inteiros, ordenados em ordem crescente \State $\textcolor{#3a7a10}{H} \gets$ heap vazio \For{$i \gets 1$ \textbf{to} $n$} \State \texttt{Insert} $A[i]$ em $\textcolor{#3a7a10}{H}$ \EndFor \For{$i \gets 1$ \textbf{to} $n$} \State $B[i] \gets$ \texttt{ExtractMin} de $\textcolor{#3a7a10}{H}$ \EndFor \EndProcedure \end{algorithmic}

Complexidade

O trabalho do HeapSort se resume a 2n operações sobre um heap de no máximo n elementos.

  • Cada operação custa \mathcal{O}(\log n), resultando em tempo total \mathcal{O}(n \log n).
  • Além disso, o vetor B não seria necessário e as linhas 4 a 5 poderiam ser substituídas por Heapify.

Desafio: Entendendo o Heapify

O que o HeapSort faz?

O HeapSort ordena um vetor inserindo seus elementos em um heap e removendo-os em ordem crescente.

Lembrando…

  • Heapify transforma um vetor qualquer (não ordenado) em um heap válido.
  • Cada operação de heap (Insert, ExtractMin) custa \mathcal{O}(\log n).
  • O HeapSort completo tem complexidade \mathcal{O}(n \log n).

Desafio

Se o HeapSort é \mathcal{O}(n \log n), como o Heapify pode ser \mathcal{O}(n)?

Implementação em Python

Ver: https://github.com/BrunoGrisci/projeto-e-analise-de-algoritmos/blob/main/paa1/dijkstra.ipynb

Mais

Além de Dijkstra

  • Algoritmo de Bellman-Ford: resolve o problema para grafos com um vértice de origem e arestas que podem ter pesos negativos.

    • \mathcal{O}(mn)

  • Algoritmo de Floyd-Warshall: determina a distância entre todos os pares de vértices de um grafo com arestas que podem ter pesos negativos (mas não ciclo negativos).

    • \mathcal{O}(n^2)

  • Algoritmo de Johnson: determina a distância entre todos os pares de vértices de um grafo em grafos esparsos. Pode haver arestas negativas, mas não ciclos negativos.

    • \mathcal{O}(n^2 \log n + mn)

  • Caminhos mínimos em DAGs: grafo acíclico dirigido.’’

  • Algoritmo A^*: um algoritmo de busca heurística que calcula o caminho mínimo com um vértice de origem.

    • \mathcal{O}(m \log n)

Além de Dijkstra

6 de agosto de 2025: https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/

Além de Dijkstra

https://arxiv.org/pdf/2504.17033

?