Programação competitiva · Grafos ponderados

Agora cada aresta pode ter um custo diferente.

Uma ligação deixa de significar apenas “existe ou não existe”. Ela pode carregar distância, tempo, preço, consumo ou qualquer outro valor.

Pesos Matriz ponderada Lista ponderada Menor custo Preparação para Dijkstra
01

O que é o peso de uma aresta?

Em um grafo ponderado, cada aresta possui um valor associado.

Distância

Estradas

Aresta A–B pode representar uma estrada de 12 km.

Tempo

Rotas

Aresta A–B pode representar 20 minutos de viagem.

Custo

Transporte

Aresta A–B pode custar R$ 8,00.

Em um grafo sem pesos, normalmente pensamos: “quantas arestas?”. Em um grafo ponderado, pensamos: “qual é a soma dos pesos?”.
02

Exemplo de grafo ponderado

Usaremos o mesmo grafo em toda a aula. Os números amarelos são os pesos das arestas.

4 2 5 1 7 3 6 2 4 A B C D E F G
Por exemplo, a aresta A–B possui peso 4, enquanto A–C possui peso 2. As duas ligações existem, mas têm custos diferentes.
03

Matriz de adjacência com pesos

Antes, a matriz guardava apenas 0 ou 1. Agora ela pode guardar o próprio peso.

Sem peso

Existe ou não existe

adj[A][B] = 1

O valor 1 apenas dizia que havia uma ligação.

Com peso

Guardamos o custo

adj[A][B] = 4

Agora sabemos que a ligação existe e custa 4.

ABCDEFG
A042∞∞∞∞
B40∞51∞∞
C2∞0∞73∞
D∞5∞0∞∞6
E∞17∞0∞2
F∞∞3∞∞04
G∞∞∞6240
Aqui usamos ∞ para representar “não existe aresta”. Em código, também é comum usar float("inf").
04

Lista de adjacência com pesos

Na lista, cada vizinho precisa vir acompanhado do peso da aresta.

A
→
(B, 4)(C, 2)
B
→
(A, 4)(D, 5)(E, 1)
C
→
(A, 2)(E, 7)(F, 3)
D
→
(B, 5)(G, 6)
E
→
(B, 1)(C, 7)(G, 2)
F
→
(C, 3)(G, 4)
G
→
(D, 6)(E, 2)(F, 4)
O par (B, 4) significa: “B é vizinho e o custo para chegar até B por esta aresta é 4”.
05

Como representar em Python

Matriz ponderada 
V = 7

INF = float("inf")

adj = [
    [INF] * V
    for _ in range(V)
]

for i in range(V):
    adj[i][i] = 0

# A --4-- B
adj[0][1] = 4
adj[1][0] = 4
Lista ponderada 
V = 7

grafo = [
    [] for _ in range(V)
]

# A --4-- B
grafo[0].append((1, 4))
grafo[1].append((0, 4))
Em programação competitiva, a lista ponderada costuma aparecer assim: grafo[v] = [(vizinho, peso), ...]
06

Agora o caminho tem custo total

O melhor caminho não é necessariamente aquele que usa menos arestas.

Caminho 1
A
4→
B
1→
E
2→
G

Custo: 4 + 1 + 2 = 7

Caminho 2
A
2→
C
3→
F
4→
G

Custo: 2 + 3 + 4 = 9

Os dois caminhos possuem 3 arestas, mas seus custos são diferentes: 7 contra 9. Em grafos ponderados, precisamos comparar a soma dos pesos.
07

Por que BFS deixa de ser suficiente?

BFS considera que cada passo tem o mesmo custo. Com pesos diferentes, isso pode levar à escolha errada.

10 2 1 A C B
Menos arestas

A → B

1 aresta, mas custo total = 10.

Menor custo

A → C → B

2 arestas, mas custo total = 3.

BFS tenderia a preferir chegar a B em uma aresta. Para pesos não negativos diferentes, o algoritmo clássico é Dijkstra.
08

Resumo

ConceitoGrafo não ponderadoGrafo ponderado
Arestaapenas ligaçãoligação + peso
Matriz0 ou 1peso ou ∞
Listavizinho(vizinho, peso)
Objetivo comummenor nº de passosmenor custo acumulado
Algoritmo típicoBFSDijkstra
Frase para memorizar: “O peso pertence à aresta. O custo de um caminho é a soma dos pesos das arestas percorridas.”