Algoritmos de Grafos

Um algoritmo de grafos recebe G=(V,E) e calcula uma ordem de visita, uma distância δ(s,v) ou uma sequência linear de V. A estrutura auxiliar — fila, pilha ou fila de prioridade — escolhe a próxima aresta a examinar.

Tempos d[u] e f[u], relaxamento e a ordem topológica deste tópico — e as árvores geradoras no tópico seguinte — reutilizam esse exame das arestas.

As páginas se agrupam em quatro blocos. O primeiro visita vértices por camadas com uma fila, ou por profundidade com uma pilha, registrando descoberta, término e o tipo de cada aresta.

O segundo lineariza um DAG: u aparece antes de v sempre que existe o arco (u,v). A fila guarda os vértices com grau de entrada restante igual a zero.

O terceiro pergunta o custo de ir de uma fonte s a cada vértice. Relaxa-se (u,v) quando d[u]+w(u,v) melhora d[v].

O quarto pergunta o custo entre todos os pares: o vértice k entra como intermediário em D^{(k)}.

Fila e distância em número de arestas a partir de s estão em Algoritmo BFS. Pilha, classificação árvore/retorno/avanço/cruzamento e DAG ⇔ sem aresta de retorno estão em Algoritmo DFS.

A fila de grau de entrada zero está em Algoritmo de Kahn. Listar vértices em tempo de término decrescente está em Algoritmo DFS.

Extrair o vértice de menor d[u] ainda aberto, quando w≥0, está em Algoritmo de Dijkstra. |V|−1 rodadas sobre todas as arestas, e a rodada extra que detecta ciclo negativo, estão em Algoritmo de Bellman-Ford.

δ(s,v) para um s fixo está em Algoritmo de Bellman-Ford. δ(i,j) para todos os pares, com diagonal negativa ⇔ ciclo negativo, está em Algoritmo de Floyd-Warshall.