Grafos Ponderados em Python: TP3 Completo com Evidência, Big-O e Casos de Borda

O que este HTML passa a fazer

Como ler o TP3 sem errar a pergunta

Protocolo fixo de evidência

O que a questão está pedindo

• Classe OO para grafo ponderado.
• Lista de adjacência com pesos.
• Métodos básicos de inserção e consulta.
• Grafo de teste com pelo menos 8 vértices e pesos distintos.
• Invariantes explícitas.

Contrato / invariantes / pré-condições

Implementação núcleo

class WeightedGraph:
    def __init__(self):
        self.adj: dict[str, dict[str, float]] = {}

    def add_vertex(self, v: str) -> None:
        if v not in self.adj:
            self.adj[v] = {}

    def add_edge(self, u: str, v: str, w: float, directed: bool = False) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u][v] = min(self.adj[u].get(v, float("inf")), float(w))
        if not directed:
            self.adj[v][u] = min(self.adj[v].get(u, float("inf")), float(w))

    def neighbors(self, u: str) -> list[str]:
        return sorted(self.adj[u].keys())

    def weight(self, u: str, v: str) -> float:
        return self.adj[u][v]

g = build_demo_graph()
assert g.neighbors("A") == ["B", "C"]
assert g.weight("A", "C") == 2.0

gd = WeightedGraph()
gd.add_edge("X", "Y", 7, directed=True)
assert gd.neighbors("X") == ["Y"]
assert gd.neighbors("Y") == []

Evidência interpretada

Big-O

O que a questão está pedindo

• BFS com fila.
• DFS com pilha ou recursão.
• Ordem determinística de visita.
• Registro explícito da estrutura usada.
• Análise de tempo e memória.

Contrato / invariantes / pré-condições

Implementação núcleo

g = build_demo_graph()
bfs_order = g.bfs("A")
dfs_order = g.dfs("A")

assert bfs_order == ['A','B','C','D','E','F','G','H']
assert dfs_order == ['A','B','C','D','E','F','H','G']

Evidência interpretada

Big-O

O que a questão está pedindo

• Executar Dijkstra no grafo ponderado.
• Calcular distâncias da origem para todos os vértices.
• Reconstruir pelo menos um caminho mínimo.
• Demonstrar com mais de uma origem.

Contrato / invariantes / pré-condições

Implementação núcleo

def path_cost(g: WeightedGraph, path: list[str]) -> float:
    return sum(g.weight(path[i], path[i + 1]) for i in range(len(path) - 1))

g = build_demo_graph()
for source, target, expected_dist, expected_path in [
    ("A", "H", 23.0, ['A','C','B','D','F','H']),
    ("D", "H", 15.0, ['D','F','H']),
    ("F", "H", 9.0, ['F','H']),
]:
    dist, prev = g.dijkstra(source)
    path = g.reconstruct_path(prev, source, target)
    assert dist[target] == expected_dist
    assert path == expected_path
    assert path_cost(g, path) == dist[target]

gneg = WeightedGraph()
gneg.add_edge("A", "B", -1, directed=False)
try:
    gneg.dijkstra("A")
    assert False
except ValueError:
    pass

Evidência interpretada

Big-O

O que a questão está pedindo

Contrato / invariantes / pré-condições

Implementação núcleo

g = build_demo_graph()
path = g.shortest_path_unweighted("A", "H")

assert path == ["A", "B", "D", "F", "H"]
assert all(path[i + 1] in g.neighbors(path[i]) for i in range(len(path) - 1))

Evidência interpretada

Big-O

O que a questão está pedindo

• Implementar Prim em grafo ponderado.
• Devolver as arestas da AGM.
• Calcular o custo total.
• Explicar o que acontece em grafo desconexo.

Contrato / invariantes / pré-condições

Implementação núcleo

g = build_demo_graph()
mst, total = g.prim("A")

assert mst == [
    ('A','C',2.0), ('C','B',1.0), ('B','D',5.0),
    ('D','E',3.0), ('D','F',6.0), ('E','G',7.0),
    ('F','H',9.0)
]
assert total == 33.0
assert total == sum(w for _, _, w in mst)
for u, v, w in mst:
    assert (v in g.adj[u] and g.adj[u][v] == w) or (u in g.adj[v] and g.adj[v][u] == w)
assert len(mst) == len(g.vertices()) - 1

Evidência interpretada

Big-O

O que a questão está pedindo

• Calcular menor caminho entre todos os pares.
• Devolver matriz final.
• Explicar o significado de verts, idx e dist.
• Demonstrar consistência com Dijkstra.

Contrato / invariantes / pré-condições

Implementação núcleo

g = build_demo_graph()
verts, idx, dist = g.all_shortest_paths_matrix()

for v in verts:
    i = idx[v]
    assert dist[i][i] == 0.0

assert dist[idx["A"]][idx["H"]] == 23.0

dA, _ = g.dijkstra("A")
for v in verts:
    assert dist[idx["A"]][idx[v]] == dA[v]

Evidência interpretada

Big-O

O que a questão está pedindo

Contrato / invariantes / pré-condições

Implementação núcleo / resposta auditável

Evidência interpretada

Big-O

O que a questão está pedindo

Contrato / invariantes / pré-condições

Implementação núcleo

g = build_demo_graph()
m = g.to_mermaid(directed=False)
print(m)

edge_lines = [ln for ln in m.splitlines() if "---|" in ln]
assert len(edge_lines) == 12
assert "A ---|2.0| C" in m or "C ---|2.0| A" in m
assert "B ---|5.0| D" in m or "D ---|5.0| B" in m
assert "G ---|12.0| H" in m or "H ---|12.0| G" in m

Evidência interpretada

Big-O

O que a questão está pedindo

• Detectar pesos inválidos.
• Detectar vértices inexistentes.
• Detectar arestas inconsistentes em simetria exigida.

Contrato / invariantes / pré-condições

Implementação núcleo

g = build_demo_graph()
g.validate_structure(require_undirected_symmetry=True)

g_bad = build_demo_graph()
g_bad.adj["A"]["Z"] = 1.0
try:
    g_bad.validate_structure()
    assert False
except ValueError:
    pass

g_bad2 = WeightedGraph()
g_bad2.add_edge("A", "B", 1, directed=True)
try:
    g_bad2.validate_structure(require_undirected_symmetry=True)
    assert False
except ValueError:
    pass

Evidência interpretada

Big-O

O que a questão está pedindo

Contrato / invariantes / pré-condições

Implementação núcleo

sizes = [20, 40, 80]
rows = []
for n in sizes:
    gg = gen_sparse_graph(n, extra_edges_per_vertex=3, seed=123)
    _, _, c = gg.dijkstra_instrumented("0")
    rows.append((n, c["heap_pop"], c["heap_push"], c["relax_attempts"], c["relax_success"]))
    print(rows[-1])

assert rows[0][3] < rows[1][3] < rows[2][3]

Evidência interpretada

Big-O

O que a questão está pedindo

Contrato / invariantes / pré-condições

Implementação núcleo

def safe_shortest_path_if_connected(g: WeightedGraph, source: str, target: str) -> list[str] | None:
    comp = g.connected_component(source)
    if target not in comp:
        return None
    dist, prev = g.dijkstra(source)
    return g.reconstruct_path(prev, source, target)

g2 = WeightedGraph()
g2.add_edge("A", "B", 1, False)
g2.add_edge("B", "C", 2, False)
g2.add_edge("X", "Y", 1, False)

assert g2.connected_component("A") == {"A", "B", "C"}
assert safe_shortest_path_if_connected(g2, "A", "Y") is None

g = build_demo_graph()
assert safe_shortest_path_if_connected(g, "A", "H") == ['A','C','B','D','F','H']

Evidência interpretada

Big-O

O que a questão está pedindo

Contrato / invariantes / pré-condições

Implementação núcleo / tabela pronta

• adj como dict[str, dict[str, float]]: ganha consulta O(1) e integração simples com Dijkstra, Prim e validação; paga memória maior que uma estrutura mais compacta.
• Determinismo por sorted(neighbors) + tie-break no heap: ganha auditoria e reprodutibilidade; paga ordenação e um contador extra.

Evidência interpretada

Big-O

Checklist de prova

• WeightedGraph: consulta de vizinhos e pesos funciona; caso dirigido demonstrado.
• BFS/DFS: ordem determinística demonstrada e estrutura de dados declarada.
• Dijkstra: distância e caminho reconstruído provados; peso negativo bloqueado.
• BFS shortest path: caminho válido em não ponderado e distinção explícita para Dijkstra.
• Prim: arestas, custo, cardinalidade e existência das arestas provados.
• Floyd: diagonal zero, leitura correta via idx e consistência com Dijkstra.
• Comparação: tabela objetiva preenchida com tempo, memória e cenário recomendado.
• Mermaid: contagem sem duplicação e arestas-chave presentes.
• Validação estrutural: caso válido e casos inválidos com exceções esperadas.
• Instrumentação: contadores reais e interpretação do crescimento empírico.
• Integração: Dijkstra não roda quando target está fora do componente.
• Cada seção contém: o que a questão pede, contrato, implementação, evidência interpretada, por que isso responde, Big-O e casos de borda.