62
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 8keyboard_arrow_downkeyboard_arrow_up

Executamos DAG-SHORTEST-PATHS para o grafo dado, usando o vértice como fonte, usando ordenação topológica. A ordenação topológica de um grafo dirigido acíclico é a ordenação linear de todos os seus nós de tal forma que se o grafo possui uma aresta , então aparece antes de . Para cada vértice processado, atualizamos as distâncias para o vértice adjacente usando a distância do vértice atual.

Passo 2 de 8keyboard_arrow_downkeyboard_arrow_up

Ordenando topologicamente o grafo dado, temos:

Imagem 1

Passo 3 de 8keyboard_arrow_downkeyboard_arrow_up

Após a execução do algoritmo, temos as seguintes alterações. Processando o vértice :

Imagem 5

Passo 4 de 8keyboard_arrow_downkeyboard_arrow_up

Processando o vértice :

Imagem 6

Passo 5 de 8keyboard_arrow_downkeyboard_arrow_up

Processando o vértice :

Imagem 7

Passo 6 de 8keyboard_arrow_downkeyboard_arrow_up

Processando o vértice :

Imagem 8

Passo 7 de 8keyboard_arrow_downkeyboard_arrow_up

Processando o vértice :

Imagem 9

Passo 8 de 8keyboard_arrow_downkeyboard_arrow_up

Por fim, processamos o vértice , alcançando o resultado final:

Imagem 10

Navegar por capítulo