Algoritmo: percurso em grafo por ordem de distância (não-ponderada) a um dado vértice de origem. Entrada: um grafo não-direcionado G, um vértice "o" de G. Saída: uma lista de pares ordenados "(v,d)", sendo "v" um vértice de "G" e "d" um número natural. ---------------------------------------------------------------------- 00. Para cada vértice v de G 01. M[v] := falso // v não foi marcado como atingido ainda. 02. 03. M[o] := verdadeiro 04. d := 0 // distância de "o" aos vértices do nível atual. 05. 06. A := fila contendo apenas "o" // "Atual": fila dos vértices do nível atual. 07. P := fila vazia // "Próximo": fila dos vértices do próximo nível. 08. S := lista vazia // "Saída": lista de saída. 09. 10. enquanto A não estiver vazia 11. u := desenfilar(A) 12. inserir o par (u,d) no final de S 13. para cada vizinho v de u 14. se M[v] = falso 15. M[v] := verdadeiro 16. enfilar(P,v) 17. se A estiver vazia 18. d := d+1 19. trocar A e P // "A" agora aponta para a fila antes apontada por "P", e vice-versa. 20. 21. retornar S ---------------------------------------------------------------------- 1. LEMA: são invariantes do laço da linha 10: a) Para todo vértice "v", se v está em A, então dist(o,v) = d. b) Para todo vértice "v", se v está em P, então dist(o,v) = d+1 e M[v] = verdadeiro. c) Para todo vértice "v", se dist(o,v) < d, então M[v] = verdadeiro. d) Se um par (v,x) está em S, então dist(o,v) = x e M[v] = verdadeiro. e) Para todo vértice "v", se v está em A, então M[v] = verdadeiro. f) Para todo vértice "v", se dist(o,v) = d, então v está em A ou v está em S. g) Para todo vértice "v", se M[v] = verdadeiro, então ou v está em A, ou em S, ou em P. h) Nenhum vértice v ocorre 2 vezes em A, nem em S, nem em P. i) Para todo par (v,x) de S, x <= d. j) Se um par (v,x) ocorre em S antes de um par (w,y), então x<=y. k) Para todo vértice "v", se dist(o,v) = d+1, então v está em P ou há em A um vizinho w de v tal que dist(o,w) = d. =================================================================== ------------------------- PROVA TEOREMA 1 ------------------------- Prova: Mostrando que as afirmações são verdadeiras logo antes da iteração zero do laço: a) A contém apenas "o" e dist(o,v) = 0 = d, cqd. b) P é vazia, logo vale por vacuidade. c) d=0, logo vale por vacuidade. d) S é vazia, logo vale por vacuidade. e) A contém apenas "o" e M[o] = verdadeiro, cqd. f) d=0, o único vértice v tal que dist(o,v) = 0 é "o", e "o" está em A. g) O único vértice marcado é "o", "o" está em A e não está em P ou S (que estão vazias). h) Verdade, pois P e S estão vazias, e "o" ocorre apenas uma vez em A. i) Verdadeira por vacuidade, já que S está vazia. j) Verdadeira por vacuidade, já que S está vazia. k) Seja v um vértice tal que dist(o,v) = d+1 vale logo antes da iteração zero do laço. Logo, como, neste ponto da execução do algoritmo, d=0, então dist(o,v) = 1, ou seja, v é vizinho de "o", e, como "o" está em "A", então a afirmação é verdadeira. Agora, suponhamos que as afirmações "a"-"k" são verdadeiras no início de uma iteração "i" qualquer, e provemos que elas são verdadeiras ao fim da iteração "i": a) Se, na iteração "i", não houve troca entre A e P, então todo vértice que está em A ao final da iteração também já estava em A logo antes da iteração, e além disso o valor de "d" não foi alterado; logo, por "a" (válida no início da iteração), todo vértice que está em A ao fim da iteração "i" está a uma distância d de o, cqd. Se, porém, houve troca entre A e P, então os elementos de A ao fim da iteração i são os que estavam em P logo antes da troca, e, além disso, d, que valia um certo natural k no início da iteração i, vale k+1 ao final da iteração. Considere agora um vértice v que está em A ao final da iteração i. Logo, v já estava em P antes da iteração i ou v foi inserido em P durante a iteração. Se v já estava em P antes da iteração i, então, por "b", dist(o,v) = k+1, cqd. Já se v foi inserido em P durante a iteração i, então v é vizinho do vértice u desenfilado na iteração i, não estava marcado no início da iteração i e está marcado ao fim da iteração. Como u estava em A no início da iteração i, então, por "a", dist(o,u) = k, e, como u e v são vizinhos, dist(o,v) <= k+1. Por "c", como v não estava marcado no início da iteração i, então dist(o,v) >= k. Além disso, por "e", v não estava em A no início da iteração i, e, por "d", v também não estava em S no início da iteração i, o que, por "f", implica que dist(o,v) != k. Logo, dist(o,v) = k+1, cqd. b) Seja um vértice "v" que pertence a P ao final de uma iteração i. Logo, na iteração i não houve troca entre A e P, pois, se tivesse havido, P estaria vazia, o que não é o caso. Logo, também não houve mudança no valor de d na iteração i, d valendo k no início e ao final da iteração. A argumentação é semelhante àquela do item anterior. Se v já estava em P antes da iteração i, então, por "b", dist(o,v) = k+1 = d+1, cqd. Se v não estava em P antes da iteração i, então v é vizinho do vértice u que foi desenfilado na iteração i, v não estava marcado no início da iteração, v passou a estar marcado no fim da iteração, e dist(o,v) = k+1, cqd (ver argumentação do item anterior). c) Se o valor de d é k no início da iteração i e continua a ser k ao fim da iteração, e então, por "c" (válida no início da iteração "i"), todo vértice v tal que dist(o,v) < d já está marcado no início da iteração e (como nenhum vértice é desmarcado pelo algoritmo) continua marcado ao fim dela. Suponha agora que o valor de d é alterado na iteração i, passando a ser k+1. Seja v tal que dist(o,v) < k+1. Se dist(o,v) < k, então, por "c", v já estava marcado no início da iteração i, e portanto continua marcado ao fim da iteração, cqd. Se, porém, dist(o,v) = k, então, por "f", no início da iteração i, v estava em A ou em S, o que, por "e" e "d", implica que "v" já estava marcado no início da iteração "i", e portanto também o está ao final da iteração, cqd. d) Seja um par (v,x) que está em S ao final de uma iteração i. Se (v,x) é o par incluído em S durante a iteração i, então v foi o vértice desenfilado de A durante a iteração, e x era o valor de d no início da iteração. Logo, v estava em A no início da iteração. Logo, por "a", dist(o,v) = x, e, além disso, por "e", v estava marcado no início da iteração i, e portanto também no final da iteração, cqd. Se, porém, (v,x) não foi incluído em S na iteração i, então esse par já pertencia a S no início da iteração; logo, por "d" (válida no início da iteração), dist(o,v) = x, e, além disso, v estava marcado no início da iteração, e portanto continua marcado ao fim dela, cqd. e) Seja um vértice v que está em A ao final de uma iteração i qualquer. Se A não foi trocada com P na iteração i, então v já estava em A no início da iteração, e, por "e", já estava marcado no início da iteração, e portanto continua marcado ao final, cqd. Se, porém, A foi trocada com P na iteração i, então ou v já estava em P no início da iteração ou foi incluído em P na iteração i. Se v já estava em P no início da iteração i, então, por "b", v já estava (e continua) marcado, cqd. Se v foi incluído em P na iteração i, então, pela linha 15 do algoritmo, v está marcado ao final da iteração i, cqd. f) Seja um vértice v tal que dist(o,v) = d ao final de uma iteração i, e seja k o valor de d no início da iteração i. Há então dois casos: ou houve troca entre A e P na iteração "i" ou não. Suponhamos primeiramente que houve troca entre A e P na iteração "i". Como, ao fim da iteração, dist(o,v) = d, e, como há troca entre A e P, então, ao fim da iteração, d=k+1, e portanto dist(o,v) = k+1. Logo, no início da iteração "i", valia dist(o,v) = k+1 = d+1, o que, pela afirmação "k", implica que, no início da iteração, v estava em P ou havia em A um vizinho w de v tal que dist(o,w) = d = k. A seguir nós mostramos que, em ambas as possibilidades, "v" estará em "A" ao fim da iteração "i", o que implica que a afirmação "f" é verdadeira ao fim da iteração "i", cqd. De fato, se "v" estava em P no início da iteração, então, pelo código do laço principal do algoritmo, "v" continuava em P até antes de ocorrer a troca entre A e P, quando então "v" passou a estar em "A", cqd. Se, por outro lado, "v" não estava em P no início da iteração, então certamente havia um vizinho "w" de "v" tal que dist(o,w) = k. Observe também que, como há troca entre A e P na iteração "i", então, no início da iteração, "A" possuía apenas um vértice, que era portanto "w", e que portanto não era "v", pois G não possui arestas com duas extremidades iguais. Além disso, no início da iteração "i" valia dist(o,v) = k+1 > d, logo, pela afirmação "i", "v" também não está em (nenhum par de) S. Logo, pela afirmação "g", "v" não estava marcado no início da iteração "i". Logo, como o vizinho "w" de "v" é o vértice que estava em "A" no início da iteração, a vizinhança ainda não marcada de "w" é incluída em "P" durante a iteração "i", o que inclui o vértice "v". Logo, por fim, quando, na iteração "i", ocorre a troca entre "A" e "P", "v" passa a estar em "A", e portanto lá está ao fim a iteração "i", cqd. Se, por outro lado, não houve troca entre A e P na iteração i, então o valor de d não mudou e, pelo invariante f, v estava em A ou em S no início da iteração i. Se v não é o vértice desenfilado na iteração i, então v continua no mesmo conjunto (A ou S), cqd. Se v é o vértice desenfilado na iteração i, então v é inserido em S e portanto está lá ao fim da iteração i, cqd. g) Seja v um vértice que está marcado ao fim de uma iteração i. Se v já estava marcado no início da iteração i, então, pela afirmação "g" (válida no início da iteração "i"), no início da iteração "i", ou "v" estava em "A", ou em "S", ou em "P". Se "v" estava em "A", há dois casos: ou "v" foi o vértice desenfilado de "A" ou não. Se "v" foi o vértice desenfilado de "A", então, ao fim da iteração "i", "v" não está em "A" (pois foi desenfilado de "A" e, pela afirmação "h", "v" não ocorria duas vezes em "A") e nem em "P" (pois, se há troca entre A e P, então P está vazia ao fim da iteração "i", e, se não há troca, então "v" não estava em P no início da iteração e nem é inserido em "P" durante a iteração, já que apenas vizinhos de "v" podem ser incluídos em P na iteração em questão), e além disso "v" estará em S, pela linha 12 do algoritmo. Logo, a afirmação "g" é válida ao fim da iteração "i", cqd. Se, por outro lado, no início da iteração "i", "v" estava em "A" mas não foi o vértice desenfilado de "A" na iteração "i", então, ao fim da iteração, "v" continuará em "A" (pois, pelo algoritmo, não é retirado de lá, e, como "A" não estará vazia, não haverá troca entre A e P durante a iteração "i"). Além disso, ao fim da iteração, "v" não estará em S, pois não estava lá no início da iteração, e, além disso, apenas o vértice desenfilado de "A" (que não é "v") é inserido em "S" na iteração em questão. Finalmente, "v" não estava em "P" no início da iteração, e também não é inserido em P durante a iteração (já que apenas vértices não marcados são inseridos em P), e, como não há troca entre A e P nessa iteração (já que "v" estará em "A", e portanto "A" não estará vazia), então "v" não estará em P ao fim da iteração, o que mostra que a afirmação "g" é verdadeira ao fim da iteração "i", cqd. Se, por outro lado, "v" não estava em "A" no início da iteração "i", e se "v" estava em "P" então há dois casos: ou houve troca entre A e P durante a iteração "i" ou não. Se não houve troca, então "v" continua em "P" ao fim da iteração, e além disso não estará em "A" (pois, como não há troca, ninguém é inserido em "A" durante a iteração, e "v" não estava em A no início da iteração), e nem em S (já que, como "v" não estava em A no início da iteração, "v" não pode ter sido o vértice que foi inserido em S durante a iteração "i"), o que mostra que a afirmação "g" é verdadeira ao fim da iteração, cqd. Se, por outro lado, houve troca entre A e P, então, novamente, ao fim da iteração, "v" não estará em S (pois, não estando em A no início da iteração, não pode ser inserido em S), e nem em P (que estará vazia ao fim da iteração, dada a troca com A), e, além disso, "v" estará em "A", dada a troca com P; logo, novamente, a afirmação "g" é verdadeira, cqd. Se, por outro lado, no início da iteração "i", "v" não estava nem em "A" e nem em "P", então, pela afirmação "g" (válida no início da iteração), "v" estava em S no início da iteração. Logo, como nenhum vértice é retirado de S, "v" estará em S ao fim da iteração. Além disso, "v" não estará em "A", pois apenas vértices que estavam em P no início da iteração poderiam ser incluídos em A durante a iteração. E, como "v" já estava marcado, "v" também certamente não é incluído em P durante a iteração, do que segue a correção da afirmação "g" ao fim da iteração "i", cqd. Suponha agora que "v" não estava marcado no início da iteração "i". Logo, pelas afirmações "e", "b" e "d", "v" não estava em A, P ou S no início da iteração "i". Além disso, pelo conteúdo do laço, v é incluído em P durante a iteração i. Se não há troca entre A e P durante a iteração "i", então, ao fim da iteração, "v" estará em P, mas não em A (pois ninguém é inserido em A na iteração e "v" não estava lá no início da iteração) ou em S (pois apenas quem estava em A no início da iteração pode ser incluído em S durante a iteração, o que não é o caso de "v"), do que segue a veracidade da afirmação "g", cqd. Se, por outro lado, há troca entre A e P, então, novamente, "v" não estará em S ao fim da iteração, e também não em P, que estará vazia, e, por fim, "v" estará em A, dada a troca; logo, a afirmação "g" é verdadeira ao fim da iteração, cqd. h) Como a afirmação "h" é verdadeira no início da iteração "i" em questão, então ela somente poderia ser falsa ao final da iteração por causa de um vértice adicionado às filas/lista em questão. Considere então um vértice "v". Se "v" é inserido em "S" durante a iteração "i", então "v" é o vértice desenfilado de "A" durante a iteração. Logo, "v" estava em "A" no início da iteração, o que, pela afirmação "e", implica que "v" estava marcado no início da iteração, o que, pela afirmação "g", implica que "v" não poderia estar em "S" no início da iteração, e portanto que, quando "v" é inserido em S ao fim da iteração, não há repetição de "v" em S. Se, na iteração "i", "v" é inserido em P e lá permanece até o fim da iteração, então não há troca entre A e P. Além disso, como "v" é inserido em "P" durante a iteração, então "v" estava desmarcado no início da iteração, e, pela afirmação "b", "v" não estava em P no início da iteração, e, portanto, "v" não ocorre duas vezes em "P" ao fim da iteração "i", cqd. Se, por fim, "v" é inserido em "A" durante a iteração "i", então necessariamente houve troca entre "A" e "P" durante a iteração "i". Assim, temos que mostrar que "v" não ocorria duas vezes em "P" antes da troca entre A e P, na linha 19 do algoritmo. De fato, há dois casos. Se "v" não foi inserido em "P" durante a iteração "i", então, pela afirmação "h", "v" ocorria no máximo uma vez em "P" no início da iteração, e portanto o mesmo vale imediatamente antes da troca entre A e P, cqd. Se, por outro lado, "v" foi inserido em "P" durante a iteração "i", então "v" não estava marcado no início da iteração, o que, pela afirmação "b", implica que "v" não estava em "P" no início da iteração, o que implica que, imediatamente antes da troca entre A e P, "v" ocorre apenas uma vez em "P", cqd. i) Seja (v,x) um par que está em S ao fim da iteração "i" do laço, e seja "k" o valor da variável "d" no início da iteração "i" em questão. Se (v,x) já estava em S no início da iteração "i", então, pela afirmação "i" (válida no início da iteração), x <= k, e, ao fim da iteração, ou d=k ou d=k+1, o que implica que x<=d ao fim da iteração, cqd. Se, por outro lado, (v,x) é o par inserido em S durante a iteração "i" em questão, então x=k e, ao fim da iteração, d=k ou d=k+1, o que implica que x<=d vale ao fim da iteração, cqd. j) Sejam (v,x) e (w,y) pares de S ao fim da iteração "i", (v,x) ocorrendo primeiro. Se ambos já ocorriam em S no início da iteração "i", então, pela afirmação "j" (válida no início da iteração "i"), x<=y, cqd. Se, por outro lado, não é verdade que ambos os pares em questão já ocorriam em S no início da iteração, então certamente (w,y) é o par que foi inserido em S na iteração "i", e então y=k, sendo "k" o valor de "d" no início da iteração. Logo, pela afirmação "i" (válida no início da iteração "i"), x <= k = y, cqd. k) Seja um vértice "v" tal que dist(o,v) = d+1 ao fim da iteração "i" em questão, e seja "k" o valor de "d" no início da iteração. Há então dois casos: ou não há troca entre A e P durante a iteração "i", ou então há essa troca. Se não há troca entre A e P durante a iteração "i", então d=k no início e no fim da iteração, e dist(o,v)=k+1. Logo, pela afirmação "k" (válida no início da iteração), no início da iteração, ou "v" está em P ou há em A um vizinho de w de v tal que dist(o,w) = d = k. Se "v" está em P no início da iteração, então, como nenhum elemento é removido de P durante a iteração (pois não há troca entre A e P), "v" está em P ao final da iteração, e portanto a afirmação "k" é verdadeira ao fim da iteração, cqd. Se, por outro lado, "v" não está em P no início da iteração, então há em A, no início da iteração, um vizinho w de v tal que dist(o,w) = d = k. São então dois casos: ou w é o vértice desenfilado de A durante a iteração "i" ou não. Se "w" não é o vértice desenfilado de A durante a iteração, então "w" continua em "A" ao fim da iteração, e, como "d" continua valendo "k" ao fim da iteração, então a afirmação "k" é verdadeira ao fim da iteração, cqd. Finalmente, se "w" é o vértice desenfilado de "A" durante a iteração "i", então nós mostraremos que "v" está em "P" ao fim da iteração, o que implica na veracidade da afirmação "k" ao fim da iteração "i", cqd. De fato, ou "v" já estava marcado no início da iteração ou não. Se "v" já estava marcado no início da iteração "i", então, pela afirmação "g", no início da iteração, ou "v" estava em "A", ou em "P", ou em "S". Além disso, como dist(o,v) = d+1 no início da iteração, então, pela afirmação "a" (válida no início da iteração), "v" não poderia estar em "A" no início da iteração. Além disso, como, no início da iteração, dist(o,v)=d+1, então, pelas afirmações "d" e "i", "v" não poderia estar em "S" no início da iteração. Logo, nós concluímos que "v" necessariamente estava em "P" no início da iteração "i", e, como não há troca entre A e P na iteração, então "v" está em P ao fim da iteração, cqd. Se, por outro lado, "v" não estava marcado no início da iteração "i", então "v" é incluído em "P" quando a vizinhança de "w" é percorrida na iteração "i", e, como não há troca entre A e P, "v" está em P ao fim da iteração "i", cqd. Suponha agora que há troca entre A e P durante a iteração "i". Logo, P é vazia ao fim da iteração "i". Nós mostraremos então que, ao fim da iteração "i", há em A um vizinho w de v tal que dist(o,w) = d = k+1. De fato, como dist(o,v) = d+1 ao fim da iteração, então dist(o,v) = (k+1)+1 = k+2, e portanto "v" possui pelo menos um vizinho "w" tal que dist(o,w) = k+1; para concluir a prova, nós mostraremos que, ao fim da iteração, "w" está em "A". Seja então um vizinho "w" de "v" tal que dist(o,w) = k+1. Logo, como d=k no início da iteração "i", então, pela afirmação "k" (válida no início da iteração "i"), no início da iteração "i", w está em P ou há em A um vizinho z de w tal que dist(o,z) = k. Se "w" está em P no início da iteração "i", então, como nenhum vértice é removido de P antes da troca entre A e P (que ocorre durante a iteração "i"), então "w" está "A" ao fim da iteração "i", cqd. Se, por outro lado, "w" não está em P no início da iteração "i", então, no início da iteração "i", há em A um vizinho z de w tal que dist(o,z) = k. Além disso, como há troca entre A e P na iteração "i", z é necessariamente o vértice que é desenfilado de A durante a iteração i. Logo, w é considerado quando a vizinhança de z é percorrida na iteração "i". Há então dois casos: ou "w" está marcado no início da iteração "i" ou não. Se "w" não está marcado, então, quando a vizinhança de z é percorrida, "w" é inserido em "P", e, com a troca de A e P que ocorre durante a iteração, "w" passa a estar em "A", cqd. Se, por fim, "w" está marcado no início da iteração "i", então, pela afirmação "g", no início da iteração "i", "w" está ou em "A", ou em "P" ou em "S". Observe então que não é possível que "w" esteja em "A" no início da iteração, pois dist(o,w) = k+1, e k+1=d+1 no início da iteração, e, se "w" estivesse em "A" no início da iteração, teríamos, pela afirmação "a", dist(o,w)=k, uma contradição. Além disso, não é possível que "w" esteja em "S" no início da iteração "i", pois, se assim fosse, então, pelas afirmações "d" e "i", dist(o,w) <= d = k no início da iteração, contradizendo o fato de que dist(o,w) = k+1. Logo, "w" necessariamente está em P no início da iteração "i", o que implica que, com a troca entre A e P, "w" estará em "A" ao fim da iteração, cqd. ------------------------- PROVA TEOREMA 1 ------------------------- ===================================================================