O enunciado do exercício é:
Prove que no início de cada iteração do algoritmo BUSCA-EM-LARGURA (o início
da iteração fica na linha 06, imediatamente antes da comparação de L com a
seqüência vazia) vale a seguinte propriedade para todo nó v : se y(v) não existe caminho de s a v de comprimento menor que y(v).
Não deveria ser igual a y(v)?
Gabriel, só corrigindo o texto acima, na apostila eu vejo:
A utilização da fila L faz com que seja feita uma busca em largura no grafo, a partir do vértice s. A condição da linha 9 garante que não sejam examinadas arestas que levem para vértices que já passaram pelo processo (ou seja, vértices j tais que y(j) < n).
A busca em largura é feita por níveis de distância de s: primeiro todos a 1 arco de distância, depois todos a 2 arcos de distância, etc. Assim, quando da atribuição da linha 10, y(v) passa a marcar o tamanho do menor caminho de s a v.
"... se y(v) < n então não existe caminho de s a v de comprimento menor que y(v)."
A utilização da fila L faz com que seja feita uma busca em largura no grafo, a partir do vértice s. A condição da linha 9 garante que não sejam examinadas arestas que levem para vértices que já passaram pelo processo (ou seja, vértices j tais que y(j) < n).
A busca em largura é feita por níveis de distância de s: primeiro todos a 1 arco de distância, depois todos a 2 arcos de distância, etc. Assim, quando da atribuição da linha 10, y(v) passa a marcar o tamanho do menor caminho de s a v.
Ai!
Não vi o não existe.
Desculpem, tudo certo...
Não vi o não existe.
Desculpem, tudo certo...