Grafos e caminhos mínimos

Um grafo G = (V, E) tem vértices e arestas. Dependências de pacotes, redes sociais, mapas e máquinas de estado são todos grafos. As representações mais comuns são a lista de adjacência (O(V + E) de espaço) e a matriz de adjacência (O(V²)).

Σ grau(v) = 2|E|      (lema do aperto de mãos)
Árvore com n vértices: exatamente n − 1 arestas, conexa e sem ciclos

Dijkstra

Com pesos não negativos, o vértice ainda não finalizado de menor distância já tem sua distância definitiva: qualquer desvio só somaria custo. Essa é a propriedade gulosa que torna o algoritmo correto.

import heapq

def dijkstra(grafo, origem):
    dist = {origem: 0}
    fila = [(0, origem)]
    while fila:
        d, u = heapq.heappop(fila)
        if d > dist[u]:
            continue                      # entrada obsoleta
        for v, peso in grafo[u]:
            nd = d + peso
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(fila, (nd, v))
    return dist                           # O((V + E) log V)

Ordenação topológica

Num grafo acíclico dirigido (DAG), existe uma ordem em que toda aresta vai “para frente”. É o que npm, make e agendadores de tarefas usam para resolver dependências. Se a ordenação falha, há um ciclo.