Exercício 24.2-2 do CLRS3 ou CLRS2. Suponha que mudamos a linha 3 de DAG-SHORTEST-PATHS para -> for os primeiros | \mathbf{V} | - \mathbf{1} vértices, tomados em ordem topológica. Mostre que o procedimento continuaria correto.

Passo 1

Enunciado resumido (o que se pede e o que é dado):
  • Temos o procedimento \text{DAG-SHORTEST-PATHS} que, originalmente, faz:
    1. inicializa d[s]=0 e d[v]=\infty para v\neq s;
    2. obtém uma ordem topológica (v_1,v_2,\dots,v_n) dos vértices de um DAG;
    3. percorre todos os vértices na ordem topológica e, para cada vértice u, relaxa todas as arestas (u,v).
  • A modificação proposta é: substituir a linha 3 por “para os primeiros |V|-1 vértices, tomados em ordem topológica, faça o laço de relaxação” — ou seja, não processar o último vértice da ordem topológica.
  • Pergunta: mostrar que, com essa modificação (ou seja, percorrendo apenas os primeiros |V|-1 vértices na ordem topológica), o procedimento continua correto (ou seja, ao final temos d[v]=\delta(s,v) para todo vértice v alcançável de s).
Informações relevantes dadas pelo enunciado:
  • O grafo é um DAG (grafo acíclico dirigido).
  • Temos uma ordem topológica (v_1,\dots,v_n).
  • A única mudança é não iterar sobre o último vértice v_n para relaxar suas arestas.
  • Mantém-se a inicialização padrão (distâncias e predecessor).

Passo 2

Conceitos e ferramentas que vamos usar (explicados de modo didático):
  • O que é \delta(s,v): é o comprimento (peso) do caminho de custo mínimo de s até v. Se v não é alcançável de s, então \delta(s,v)=\infty.
  • O que faz a operação RELAX (u,v,w): se d[v] > d[u] + w(u,v) então atualiza d[v] \leftarrow d[u] + w(u,v) e \pi[v]\leftarrow u. Ou seja, tenta melhorar a estimativa d[v] usando o caminho que passa por u.
  • Propriedade útil da relaxação: se ao relaxar (u,v) já temos d[u]=\delta(s,u), então após relaxar teremos d[v] \le \delta(s,u)+w(u,v). Repetindo adequadamente para todos predecessores, podemos alcançar d[v]=\delta(s,v).
  • O que garante uma ordem topológica: para toda aresta (x,y) vale que x aparece antes de y na ordem topológica. Em particular, o último vértice v_n da ordem topológica não tem arestas saindo para vértices posteriores (pois não há posteriores) — logo v_n não tem arestas saindo (ou, equivalentemente, não tem arestas (v_n,\cdot) que precisem ser relaxadas para alcançar outros vértices).
Vou usar uma prova por indução sobre a posição de um vértice na ordem topológica — é o método natural aqui porque a propriedade que queremos (distâncias finais calculadas) se propaga ao longo da ordem topológica.

Passo 3

Estabelecendo o invariante a ser provado por indução:
Invariante a provar: após relaxarmos as arestas de todos os vértices v_1,\dots,v_k (os primeiros k vértices da ordem topológica), vale que, para todo i\le k,
d[v_i] = \delta(s,v_i).
Vou provar esse invariante por indução sobre k (índice na ordem topológica). Este invariante é exatamente o que garante a correção: quando k=n-1 (isto é, depois de processar os primeiros |V|-1 vértices), teremos as distâncias finais para todo vértice dentre os primeiros n-1; preciso também argumentar que isso já garante a distância correta do último vértice v_n.

Passo 4

Base da indução ( k=1) — explicação detalhada:
Considere v_1, o primeiro vértice na ordem topológica. Existem duas possibilidades relevantes:
  • Se v_1 = s (a fonte), então a inicialização colocou d[v_1]=d[s]=0, que é \delta(s,v_1)=0.
  • Se v_1 \neq s, então qualquer caminho de s a v_1 teria que passar por vértices que aparecem antes de v_1 na ordem topológica; como v_1 é o primeiro, não há predecessores na ordem topológica, logo não existe caminho de s a v_1 (ou seja, v_1 não é alcançável de s). Então \delta(s,v_1)=\infty, e a inicialização tinha d[v_1]=\infty.
    Portanto, imediatamente após (ou antes de) processar v_1 (e relaxar suas arestas), vale d[v_1]=\delta(s,v_1). Assim a base está bem estabelecida.
Obs.: não precisamos que v_1 tenha sido relaxado para que sua própria distância esteja correta — a inicialização já garante isso no caso de ser inalcançável, e se for a própria fonte, também já está correta.

Passo 5

Passo indutivo ( k \to k+1) — demonstração detalhada:
Hipótese indutiva: suponha que, após processarmos (isto é, relaxarmos as arestas de) os primeiros k vértices v_1,\dots,v_k, temos d[v_i]=\delta(s,v_i) para todo i\le k.
Queremos mostrar que, depois de também processar v_{k+1}, teremos d[v_{k+1}]=\delta(s,v_{k+1}).
Raciocínio:
  • Todo caminho de s até v_{k+1} (se existir) termina vindo por alguma aresta (u,v_{k+1}) cujo vértice u aparece antes de v_{k+1} na ordem topológica. Ou seja, u tem índice i\le k.
  • Pelo enunciado da hipótese indutiva, para cada tal predecessor u temos d[u]=\delta(s,u) após termos processado os primeiros k vértices.
  • Quando processamos cada predecessor u (isto é, quando relaxamos suas arestas), a aresta (u,v_{k+1}) foi relaxada e então ofereceu à v_{k+1} a possibilidade de atualizar d[v_{k+1}] para d[u]+w(u,v_{k+1})=\delta(s,u)+w(u,v_{k+1}).
  • Tomando o mínimo sobre todos esses predecessores u, após termos processado todos os v_1,\dots,v_k teremos d[v_{k+1}] \le \min_{(u,v_{k+1})} \big(\delta(s,u) + w(u,v_{k+1})\big).Mas o lado direito é exatamente a definição de \delta(s,v_{k+1}) (caminho mínimo que chega em v_{k+1} pela última aresta), logo d[v_{k+1}] \le \delta(s,v_{k+1}).
  • Como por definição sempre vale d[v_{k+1}] \ge \delta(s,v_{k+1}) (a relaxação nunca cria um valor menor que o mínimo possível), concluímos d[v_{k+1}] = \delta(s,v_{k+1}).
Assim o invariante vale para k+1. Isso completa a indução.

Passo 6

Concluindo por que processar só os primeiros |V|-1 vértices é suficiente:
  • Pelo passo anterior, após processarmos os primeiros n-1 vértices v_1,\dots,v_{n-1} teremos d[v_i]=\delta(s,v_i) para todo i\le n-1.
  • O último vértice v_n da ordem topológica tem todas as suas arestas incidentes vindas de vértices com índice <n (predecessores entre v_1,\dots,v_{n-1}). Portanto, enquanto procesávamos esses predecessores nós já relaxamos todas as arestas (u,v_n) que podem estabelecer d[v_n]. Assim, ao final de processar v_1,\dots,v_{n-1} já se tem d[v_n]=\delta(s,v_n).
  • Alternativamente, observar que v_n não possui arestas saindo que apontem para vértices posteriores (pois não há posteriores), logo não há necessidade de relaxar arestas a partir de v_n para corrigir distâncias de outros vértices — não há outros vértices após v_n que dependam de relaxações de (v_n,\cdot).
  • Portanto, deixar de processar (relaxar arestas de) o último vértice v_n não impede que todas as distâncias finais d[v] sejam corretas.
Logo o procedimento modificado (percorrer apenas os primeiros |V|-1 vértices em ordem topológica) produz as distâncias corretas d[v]=\delta(s,v) para todo v.

Passo 7

Um pequeno exemplo ilustrativo (bem simples, para fixar a ideia):
Considere DAG com ordem topológica (v_1,v_2,v_3) e arestas (v_1,v_2),(v_2,v_3). Processando v_1 relaxamos (v_1,v_2) e fixamos d[v_2] se houver caminho ótimo via v_1. Depois processando v_2 relaxamos (v_2,v_3) e fixamos d[v_3]. Note que v_3 é o último; ele não tem arestas saindo (na ordem dada). Se pararmos depois de processar v_1,v_2 (os primeiros |V|-1=2 vértices), já temos d[v_1],d[v_2],d[v_3] corretos — não era preciso processar v_3.

Resposta

Sim. A modificação continua correta: processar apenas os primeiros |V|-1 vértices em ordem topológica é suficiente para que, ao final, d[v]=\delta(s,v) para todo vértice v.

Exercícios relacionados