back to lab notes
algorithmscompleted2024
Graph Algorithms for OBI
Repositório de simulação e treino para a OBI (2019, 2021, 2023). 16 arquivos com simulações de estado, análise combinatória e grafos com ênfase em Big-O.
PythonCAlgorithmsOBIGraphs
Specifications
Linguagens
Python 3 · C
Arquivos
16 implementações
Edições OBI
2019, 2021, 2023
Bellman-Ford
O(V·E) tempo
Dijkstra
O(V²) s/ heap
Resultado
🥉 Bronze OBI 2024
Tech Stack
Python 3Ctimeitheapqcollections
Overview
16 implementações cobrindo simulações de estado, análise combinatória e algoritmos de grafos. Bellman-Ford com relaxamento massivo de arestas (V-1 iterações) para suporte a pesos negativos e detecção de ciclos. Dijkstra guloso com arrays auxiliares (distances[], parents[]) para reconstrução retroativa de trajeto. Benchmarking via timeit para comparação de list.sort() vs sorted(dict) com lambda.
Key Features
- Bellman-Ford: O(V·E), relaxamento massivo, detecção de ciclos negativos
- Dijkstra: O(V²) s/ heap, reconstrução de caminho via parents[]
- Chuva (OBI 2019): propagação matricial O(N²), varredura direcional
- Tempo (OBI 2021): simulação temporal com filas e dicionários de eventos
- Contas & Leilão (OBI 2023): algoritmos gulosos O(N log N) com tuplas dinâmicas
- Benchmarking: timeit para medir ms de diferença entre estruturas de dados
Dijkstra — Menor Caminho Ponderado
python
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
parents = {start: None}
pq = [(0, start)]
while pq:
dist, node = heapq.heappop(pq)
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
parents[neighbor] = node
heapq.heappush(pq, (new_dist, neighbor))
return distances, parents