Exercício 24.2-2 do CLRS3 ou CLRS2. Suponha que mudamos a linha 3 de DAG-SHORTEST-PATHS para -> for os primeiros |
| -
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
que, originalmente, faz: - inicializa
e para ; - obtém uma ordem topológica
dos vértices de um DAG; - percorre todos os vértices na ordem topológica e, para cada vértice
, relaxa todas as arestas .
- inicializa
- A modificação proposta é: substituir a linha 3 por “para os primeiros
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értices na ordem topológica), o procedimento continua correto (ou seja, ao final temos para todo vértice alcançável de ).
Informações relevantes dadas pelo enunciado:
- O grafo é um DAG (grafo acíclico dirigido).
- Temos uma ordem topológica
. - A única mudança é não iterar sobre o último vértice
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 é
: é o comprimento (peso) do caminho de custo mínimo de até . Se não é alcançável de , então . - O que faz a operação RELAX
: se então atualiza e . Ou seja, tenta melhorar a estimativa usando o caminho que passa por . - Propriedade útil da relaxação: se ao relaxar
já temos , então após relaxar teremos . Repetindo adequadamente para todos predecessores, podemos alcançar . - O que garante uma ordem topológica: para toda aresta
vale que aparece antes de na ordem topológica. Em particular, o último vértice da ordem topológica não tem arestas saindo para vértices posteriores (pois não há posteriores) — logo não tem arestas saindo (ou, equivalentemente, não tem arestas 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
(os primeiros
vértices da ordem topológica), vale que, para todo
,
Vou provar esse invariante por indução sobre
(índice na ordem topológica). Este invariante é exatamente o que garante a correção: quando
(isto é, depois de processar os primeiros
vértices), teremos as distâncias finais para todo vértice dentre os primeiros
; preciso também argumentar que isso já garante a distância correta do último vértice
.
Passo 4
Base da indução (
) — explicação detalhada:
Considere
, o primeiro vértice na ordem topológica. Existem duas possibilidades relevantes:
- Se
(a fonte), então a inicialização colocou , que é . - Se
, então qualquer caminho de a teria que passar por vértices que aparecem antes de na ordem topológica; como é o primeiro, não há predecessores na ordem topológica, logo não existe caminho de a (ou seja, não é alcançável de ). Então , e a inicialização tinha .
Portanto, imediatamente após (ou antes de) processar(e relaxar suas arestas), vale . Assim a base está bem estabelecida.
Obs.: não precisamos que
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 (
) — demonstração detalhada:
Hipótese indutiva: suponha que, após processarmos (isto é, relaxarmos as arestas de) os primeiros
vértices
, temos
para todo
.
Queremos mostrar que, depois de também processar
, teremos
.
Raciocínio:
- Todo caminho de
até (se existir) termina vindo por alguma aresta cujo vértice aparece antes de na ordem topológica. Ou seja, tem índice . - Pelo enunciado da hipótese indutiva, para cada tal predecessor
temos após termos processado os primeiros vértices. - Quando processamos cada predecessor
(isto é, quando relaxamos suas arestas), a aresta foi relaxada e então ofereceu à a possibilidade de atualizar para . - Tomando o mínimo sobre todos esses predecessores
, após termos processado todos os teremos Mas o lado direito é exatamente a definição de (caminho mínimo que chega em pela última aresta), logo - Como por definição sempre vale
(a relaxação nunca cria um valor menor que o mínimo possível), concluímos .
Assim o invariante vale para
. Isso completa a indução.
Passo 6
Concluindo por que processar só os primeiros
vértices é suficiente:
- Pelo passo anterior, após processarmos os primeiros
vértices teremos para todo . - O último vértice
da ordem topológica tem todas as suas arestas incidentes vindas de vértices com índice (predecessores entre ). Portanto, enquanto procesávamos esses predecessores nós já relaxamos todas as arestas que podem estabelecer . Assim, ao final de processar já se tem . - Alternativamente, observar que
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 para corrigir distâncias de outros vértices — não há outros vértices após que dependam de relaxações de . - Portanto, deixar de processar (relaxar arestas de) o último vértice
não impede que todas as distâncias finais sejam corretas.
Logo o procedimento modificado (percorrer apenas os primeiros
vértices em ordem topológica) produz as distâncias corretas
para todo
.
Passo 7
Um pequeno exemplo ilustrativo (bem simples, para fixar a ideia):
Considere DAG com ordem topológica
e arestas
. Processando
relaxamos
e fixamos
se houver caminho ótimo via
. Depois processando
relaxamos
e fixamos
. Note que
é o último; ele não tem arestas saindo (na ordem dada). Se pararmos depois de processar
(os primeiros
vértices), já temos
corretos — não era preciso processar
.
Resposta
Sim. A modificação continua correta: processar apenas os primeiros
vértices em ordem topológica é suficiente para que, ao final,
para todo vértice
.