Grafos com Pesos

// COS 242 · Teoria dos Grafos · 2026/2

Grafos com pesos, Dijkstra e caminhos mínimos

Trabalho de disciplina, Parte 2: a biblioteca C++ estendida para pesos reais, com três estruturas de prioridade e estudos de caso até 50 milhões de vértices.

DuplaJoão Costa · Miguel Cerne

InstituiçãoUFRJ · Escola Politécnica

Códigogithub.com/Cerne17/graph-library-cpp

// escopo

O que o enunciado pede — e o que foi entregue

Grafos não direcionados com pesos reais

Leitor aceita u v peso, valida IDs, descarta laços e os contabiliza

CSR e matriz, escolhidos em compilação

Dijkstra por vetor e por heap atualizável

Uma interface, estruturas trocáveis; pesos negativos → aviso de “não implementado”

implementados e testados
+ 3ª versão de comparação

Distâncias e caminhos: 10 → 20…60 e a rede de colaboração

Caminho completo por destino, grafias exatas dos pesquisadores

25 + 5 pares completos

Tempo médio das duas versões, k = 100 origens

Heap medido em todos os grafos; vetor medido no Grafo Ponderado 3

pendente: vetor nos grafos 4 a 7

// arquitetura

Políticas, conceitos e funções livres

diagrama da biblioteca · animado

// dados

Os seis grafos ponderados

Grafo	Vértices	Arestas	δ (%)	Comp.	Grau med.	Peso méd.	Pesos 0
Ponderado 3	100.000	6.099.941	0,122	1	122	4,96	3.074
Ponderado 4	1.000.000	30.999.978	0,0062	1	62	4,92	15.950
Ponderado 5	10.000.000	39.999.995	0,00008	1	8	4,37	24.894
Ponderado 6	10.000.000	73.403.372	0,00015	4	15	5,00	36.410
Ponderado 7	50.000.000	59.999.999	0,0000048	1	2	2,92	55.177
Rede colab.	722.385	2.272.543	0,00087	77.486	3	5,18	0

δ = 2·M_u / N(N−1)

≤ 0,122%

dos pares possíveis, em todos os seis: grafos esparsos.

Pesos em [0, 10]

Ponderados 3–7 têm pesos zero; a rede vai de 0,0037 a 113. Nenhum peso negativo nas entradas.

Como na Parte 1, M > N em todos: são as arestas que dominam memória e tempo. A exceção estrutural é a rede, com 43.576 vértices isolados.

// estrutura

O que usamos: CSR ponderado

tipo usado em todos os estudos de caso

csr_graph<undirected, weighted<double>>

Grafos muito esparsos: densidade de no máximo 0,122%
Só arestas existentes, nos dois sentidos: 24 B por aresta
Matriz ponderada: 1 double por par de vértices; não cabe nem no menor grafo
Matriz com bitmask segue na biblioteca para grafos sem peso

Layout e memória em detalhe: apêndice A1 e A2.

Ponderados 6 e 7 ocupam o mesmo ≈ 1,7 GiB com 5× mais vértices no 7: como na Parte 1, quem manda é M (24 B por aresta contra 8 B por vértice).

// algoritmo

Dijkstra com heap indexado

template<weighted_graph G>shortest_paths<typename G::weight_type>dijkstra_heap(const G& g, vertex_id source){  detail::check_dijkstra_input(g, source);  auto sp = detail::init_shortest_paths(g, source);   indexed_min_heap<W> heap(g.vertex_count());  heap.push(source, W{ 0 });  while (!heap.empty()) {    const vertex_id u = heap.pop();    g.for_each_edge(u, [&](vertex_id v, W w) {      const W nd = sp.dist[u] + w;      if (nd < sp.dist[v]) {        sp.dist[v] = nd;        sp.parent[v] = u;        if (heap.contains(v)) heap.update_key(v, nd);        else                  heap.push(v, nd);      }    });  }  return sp;}

1 · entrada

Peso negativo → std::invalid_argument: a biblioteca ainda não implementa esse caso. Checagem em O(1).

2 · estado inicial

dist = +∞, parent = 0, dist[s] = 0. Igual nas três versões.

3 · extração

Com pesos ≥ 0, quem sai do heap tem distância final.

4 · relaxação estrita

Empate não troca o pai. Já no heap: update_key em O(log N).

5 · saída

{source, dist, parent}; reconstruct_path segue os pais.

// trade-offs

Onde ficam as estimativas: três escolhas

vetor

heap indexado

entradas obsoletas

// resultados

Tempo médio por origem

dados reais · 100 origens · Azure

Azure Standard_E4as_v4 · k = 100 origens, semente 2025 · cronometrada só a chamada do Dijkstra · vetor não medido nos Ponderados 4–7 (≠ zero)

O assintótico explica vetor × heap (224×), mas não heap × obsoletas: nos grafos grandes, a fila com entradas obsoletas foi até 2,71× mais rápida.

// estrutura

Componentes separam média e mediana

Grafo	Comp.	Maior comp.	Heap · média	Heap · mediana	Obsol. · média	Obsol. · mediana
Ponderado 3	1	100.000	0,118	0,118	0,154	0,154
Ponderado 4	1	1.000.000	2,14	2,13	2,04	2,04
Ponderado 5	1	10.000.000	23,69	23,71	12,83	12,83
Ponderado 6	4	9.999.997	27,75	27,79	17,95	17,99
Ponderado 7	1	50.000.000	110,91	111,10	40,93	40,96
Rede colab.	77.486	576.309	0,374	0,474	0,241	0,308

segundos por origem · 100 origens, semente 2025

O(N) + O((N_c + M_c) log N_c)

Revisão da Parte 1: dist, parent, key_ e pos_ têm tamanho N, então toda busca paga a inicialização, mesmo numa componente pequena.

≈ 20%

dos vértices da rede estão fora da componente gigante: essas origens terminam cedo e puxam a média para baixo.

Com uma componente, média e mediana diferem menos de 1%. Com 77.486 componentes, a média fica 21% abaixo da mediana: o mesmo efeito que, na Parte 1, nos fez reportar as duas.

// estudo de caso 1

Origem 10 → destinos 20, 30, 40, 50, 60

dados reais · caminhos exportados

distância

arestas

peso médio

Distância é soma de pesos, não contagem de arestas: no Ponderado 7, o destino 40 exige 46 arestas (d = 100,69); o 60, com 36, fica mais perto (d = 82,25).

// estudo de caso 2

Edsger W. Dijkstra → cinco pesquisadores

dados reais · rede de colaboração

Como as células vazias da Parte 1: Turing está em outra componente, então d = +∞ e não há caminho. Não é erro nem nome desconhecido.

// coerência

O que mantivemos e o que revisamos da Parte 1

Parte 1 dizia	Parte 2	Situação
BFS mais rápida que DFS	Confirmado na nova rodada em CSR, nos 12 grafos	mantido
Matriz inviável nos Grafos 3 a 6	Com bitmask (1 bit por par), 3 e 4 cabem em ≈ 16,4 GiB; 5 e 6 pediriam ≈ 2.731 GiB	ampliado
Busca custa O(N_cc + M_cc)	O(N + N_c + M_c): os vetores têm tamanho N e são inicializados em toda busca	corrigido
Arestas como lidas do arquivo	Laços descartados e contados (Grafo 2: 65 laços, 1.299.729 válidas)	corrigido
“Algoritmos viram métodos de Graph”	Funções livres sobre conceitos (slide 3)	mudou o plano
Diâmetro inversamente ligado ao grau mediano	Sem generalizar: densidade maior não garante diâmetro menor entre grafos distintos	restrito

As mudanças vêm da implementação (laços, bitmask, inicialização), não de dados trocados: tudo está reconciliado no material complementar.

// validação

Como sabemos que está certo

178

casos de teste C++

Execução Linux com sanitizadores

3 = 3

testes diferenciais

As versões concordam; com pesos unitários, distância = nível da BFS

160

resultados à mão

11 grafos: pesos zero/negativos, empates, paralelas, inalcançáveis, reduções de chave

Lacuna aberta

O tempo da versão por vetor nos Grafos Ponderados 4 a 7 ainda precisa de uma rodada própria. “Não medido” não é zero nem estimativa, e a versão com entradas obsoletas não preenche essa lacuna.

// obrigado

Perguntas?

João Costa · Miguel Cerne

Teoria dos Grafos · UFRJ · 2026/2

github.com/Cerne17/graph-library-cpp

// apêndice

Material complementar

A1 · layout do CSR conforme as políticas

A2 · memória: CSR × matriz

A3 · Dijkstra passo a passo

A4 · heap indexado: update_key

A5 · tempos detalhados

A6 · protocolo experimental

// apêndice A1 · implementação

Um tipo de grafo, montado em compilação

layout real da biblioteca

direção

peso

Contratos graph_like e weighted_graph: conceitos, não classes abstratas
Buscas e Dijkstra são funções livres sobre o contrato

// apêndice A2 · representação

Por que CSR: a matriz ponderada não cabe

dados reais · RSS no Azure

Clique numa linha do gráfico. Eixo em escala log, potências de 1024.

// apêndice A3 · demo

Dijkstra passo a passo, nas três estruturas

simulação do algoritmo da biblioteca

estrutura

vel.

// apêndice A4 · estrutura de dados

Heap indexado: update_key em O(log N)

simulação · mesma lógica de heap.hpp

vértice selecionado — · chave atual —

nova chave 0

trocas na última operação0

altura ⌊log₂ n⌋3

// apêndice A5 · resultados

Tempo médio por origem, 100 origens

dados reais · Azure

vetor heap indexado entradas obsoletas

// apêndice A6 · método

Como os tempos foram medidos

máquina

Azure Standard_E4as_v4

4 vCPUs AMD EPYC 7763 · 32 GiB · belgiumcentral · g++ 13.3 · commit b414456

amostra

k = 100 origens, semente 2025

Mesma sequência para as três versões; a ordem das versões alterna a cada origem

intervalo medido

Só a chamada do Dijkstra

Inclui alocações da busca; exclui leitura, descompactação, validação e exportação

Grafos: Ponderados 3 a 7 (10⁵ a 5·10⁷ vértices, até 7,3·10⁷ arestas) e a rede de colaboração (722.385 pesquisadores). Todos em CSR.

← → espaço	navegar
Home / End	primeiro / último
T	iniciar/pausar cronômetro
R R	zerar cronômetro
N	notas do apresentador
F	tela cheia
D	tema claro/escuro
P	exportar PDF (com keyframes)
?	esta ajuda
Esc	fechar painéis