64
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 3keyboard_arrow_downkeyboard_arrow_up

Devemos aplicar os códigos SLOW-ALL-PAIRS-SHORTEST-PATHS e FASTER-ALL-PAIRS-SHORTEST-PATHS no grafo ponderado da Figura 25.2.

Passo 2 de 3keyboard_arrow_downkeyboard_arrow_up

O seguinte código deve ser implementado:

#include< stdio.h>// Variedade de vertices do grafo#define V four/* Definimos infinito como um valor muito maior que os usados. Esse valor é usado para vertices desconectados */#define INF 99999// Operação para exibir a matriz de respostavoid printSolution(int dist[][V]);void floydWarshall (int graph[][V]){    /* dist[][] são as matrizes de resposta que podem ter a menor distância entre cada tentativa de vértices */    int dist[V][V], i, j, k;    /* Inicializa a matriz de resposta como a mesma que a matriz de entrada de grafos*/    for (i = 0; i < V; i++)        for (j = 0; j < V; j++)            dist[i][j] = graph[i][j];    /* Adiciona todos os vértices um a um para o conjunto de vértices */    for (k = 0; k < V; k++)        for (i = 0; i < V; i++)            for (j = 0; j < V; j++)                if (dist[i][k] + dist[k][j] < dist[i][j])                    dist[i][j] = dist[i][k] + dist[k][j];            }        }    }    // Exibe a matriz de menor distância    printSolution(dist);}/* Uma função para exibir a resposta */void printSolution(int dist[][V]){    printf ("A seguinte matriz mostra as menores ditâncias"            " entre cada um dos vértices \n");    for (int i = 0; i < V; i++)       int graph[V][V] = ,                        ,                        ,                                             };    // Exibe a resposta    floydWarshall(graph);    return 0;}

Passo 3 de 3keyboard_arrow_downkeyboard_arrow_up

Portanto, está feita a implementação dos .

Navegar por capítulo