investigacao operacional 2

Prévia do material em texto

Índice 
1. Introdução ................................................................................................................................ 2 
2. Árvore Geradora ...................................................................................................................... 2 
2.1. Algoritmo da Árvore Geradora Mínima........................................................................... 3 
2.1.1. Algoritmo de Kruskal ............................................................................................... 4 
2.1.2. Algoritmo de Prim .................................................................................................... 6 
3. Problema do caminho mais curto .......................................................................................... 10 
3.1. Algoritmos para a resolução de caminho mínimo .......................................................... 11 
3.1.1. Algoritmo de Dijkstra ............................................................................................. 11 
3.1.2. Algoritmo de Floyd ................................................................................................. 15 
4. Conclusão .............................................................................................................................. 20 
5. Referências Bibliográficas ..................................................................................................... 20 
 
 
2 
 
1. Introdução 
O presente trabalho tem como tema Algoritmo da Árvore Geradora Mínima, apresenta-se uma 
classe de grafos conexos – a classe das árvores. O facto da resolução de muitos problemas 
associados a grafos se fazer com recurso a árvores, faz desta classe uma das mais importantes na 
Teoria dos Grafos. Os primeiros estudos sobre árvores foram realizados pelo matemático britânico 
Arthur Cayley em 1857, pelo que o reconhecimento da sua importância vem praticamente desde 
as origens da Teoria dos Grafo. O problema da árvore geradora mínima aparece em uma série de 
aplicações, ou como um subproblema destas. Como uma grande quantidade de situações de 
pesquisa operacional pode ser modelada e resolvida com o uso de redes há uma variedade de 
algoritmos de otimização em redes, segundo Taha (2010), os quatro principais são árvore geradora 
mínima que objectiva diminuir custos dentro de uma rede em que os nós são ligados dois a dois, 
algoritmo do caminho mínimo usado para definir o menor caminho entre os nós de origem e 
destino. 
2. Árvore Geradora 
Uma árvore consiste na interligação entre os nós de uma rede que não formem um ciclo. Ciclo é 
quando podemos conectar o no 3, para o no 4, do no 4 para o 2, e assim sucessivamente, formando 
um ciclo entre o 3, o 4 e o 2. Arco orientado (aresta orientada), representado por seta ou dirigido 
(dirigida) representado por linha é um arco que permite fluxo positivo em uma direcção e fluxo 
zero na direcção oposta. Uma rede orientada é aquela na qual todos arcos são orientados. 
Toda vez que quisermos formar uma árvore, queremos especificar qualquer ligação entre os nos 
1,2 e 3, mas sem formar um ciclo, se fizéssemos uma linha que ligasse o 1 ao 3, e a representação 
deixaria de ser uma árvore. Mas poderíamos se quiséssemos tirar a linha de 1 para 2 e fazer uma 
linha no nó 1 para o no 3 e do no 3 para o no 2, e sem formara ciclo entre eles. 
 
 
 
Árvore 
1 
2 
3 
3 
 
Uma árvore geradora é uma árvore, só que interligando todos os nós, mas ela não pode gerar ciclo 
e ela tem que interligar os nós, na pratica é um subconjunto da rede, escolhe – se algumas dessas 
ligações formando uma arvore que interliga todos os nós da rede, pega –se os ramos: Poderíamos 
pegar qualquer outro ramo desde que interligasse todos os nós e não formar ciclos e obviamente 
que seja ramos que formam a nossa rede original, não podemos inventar uma ligação tipo por 
exemplo: do 1 para o 5, porque na nossa rede não há ligação do 1 directo ao 5, por isso chama – 
se subconjunto da rede original. 
 
 
 
 
Árvore geradora 
2.1.Algoritmo da Árvore Geradora Mínima 
Colin (2007) define árvore geradora mínima como sendo árvores geradoras que possuem um 
comprimento mínimo e suas aplicações estão associadas à construção de redes de comprimento 
mínimo e também em ciclos. É possível observar problemas modelados de acordo com essa 
definição em exemplos como: redes de telecomunicações, redes de transporte como estradas e 
linhas férreas, projetos de redes de distribuição de água e esgoto, redes de distribuição de 
eletricidade, circuitos integrados, entre outros. 
De acordo com Hillier e Lieberman (2013), o algoritmo para o problema da árvore geradora 
mínima pode ser resolvido considerando primeiro a seleção de qualquer nó para começar. Assim, 
o estágio inicial compreende selecionar a ligação mais curta possível para outro nó desconectado. 
Posteriormente, verifica-se qual nó desconectado que está mais próximo de qualquer nó conectado 
e faz-se a ligação a ele, sendo que o procedimento se repete até que todos os nós estejam 
conectados. Caso haja empates na seleção de nós, deve-se resolver de forma arbitrária, sendo que 
o algoritmo ainda será capaz de prover uma solução ótima. 
Segundo Hillier e Lieberman (2006), Para resolução desse tipo de problema de rede pode –se 
utilizar dois algoritmos: Algoritmo de Prim e Algoritmo de Kruskal. 
1 
2 
3 
4 
5 
4 
 
O problema de Árvores Geradoras Mínimas também conhecida como “Árvore Geradora de Custo Mínimo” 
possui várias aplicações na atualidade, como por exemplo, projeto de redes de telecomunicação, fibra-ótica, 
redes de telefonia, projeto de rodovias, ferrovias, entre outros. Essas aplicações consistem na construção de 
grafos e resolução com algoritmos, como o Algoritmo de Prim e o Algoritmo de Kruskal. 
2.1.1. Algoritmo de Kruskal 
O algoritmo de Kruskal é utilizado para gerar árvores geradoras de custo mínimo em grafos 
desconexos. Inicialmente cada componente de um grafo é composta por apenas um vértice, na qual 
faz crescer uma floresta geradora se tornando conexa. O resultado é um conjunto de uma ou mais 
árvores. O algoritmo de Kruskal começa com uma floresta de árvores formadas por apenas um 
vértice e procura, a cada passo, uma aresta que, além de conectar duas árvores distintas da floresta, 
possua peso mínimo. 
O Algoritmo de Kruskal é um algoritmo que é usado em teoria de grafos. Este grafo tem arestas e 
pesos é um grafo ponderado ou pesado porque as arestas estão associadas a um certo valor temos 
aqui os pesos do grafo, o nosso objectivo é encontrar uma árvore ou seja um subgrafo, e este 
subgrafo deve abranger todos os vértices e ao mesmo tempo deve apresentar um custo mínimo, o 
que é isso de custo mínimo?, custo mínimo é quando nos somamos os pesos de cada aresta e vamos 
ter um valor mínimo possível, esse que é o nosso problema neste caso, ao se determinar a árvore 
abrangente, nós temos que somar os pesos e esses pesos devem apresentar um valor mínimo 
possível, um custo mínimo, o Algoritmo de Kruskal vem exatamente para responder a esta questão. 
Este algoritmo consiste em: 
Passo 1: Colocar ou dispor em ordem crescente as arestas em função do seu peso, isto é, temos o 
nosso grafo, então iremos analisar as arestas e analisamos também os seus pesos, por exemplo a 
aresta 𝑣2 e aresta 𝑣3 tem um peso 3, que é o valor mínimo possível de todos os pesos que estão 
nessa rede então sera a nossa primeira aresta. Estamos a dispor as arestas em ordem crescente dos 
seus pesos, em caso de coincidência nos pesos podemos escolher de forma arbitraria. 
 
 
 
5 
 
 
 8 3 
 7 5 
 9 
 4 4 
 7 
 6 
 
 
Arestas 𝒗𝟐𝒗𝟑 𝑣3𝑣4 𝑣1𝑣5 𝑣2𝑣4 𝑣5𝑣6 𝑣1𝑣6 𝑣2𝑣5 𝑣2𝑣6 𝑣1𝑣4 
Pesos 3 4 4 5 6 7 7 8 9 
 
Passo 2: consiste mais em logica e observação, iremos considerar as arestas em ordem crescente e 
evitando ciclos, então para tal teremos que entrar em consonânciajunto com a tabela e a nossa 
representação do grafo, o peso 3 que é da aresta 𝑣2 e aresta 𝑣3, sera pintada para facilitar a sua 
visualização, esta aresta entra para o nosso grafo, o nosso subgrafo, a nossa árvore geradora 
mínima, a próxima aresta é da aresta 𝑣3 e aresta 𝑣4, que tem custo 4, a próxima aresta sera a da 
aresta 𝑣1 e aresta 𝑣5, também com custo 4, a próxima é a da aresta 𝑣2 e aresta 𝑣4, com custo 5 ( 
porem se formos a unir as arestas 𝑣2 e 𝑣4 iremos perceber que iremos formar um ciclo, logo nos 
não podemos formar um ciclo, temos que evitar os ciclos, por tanto está aresta 𝑣2 e 𝑣4, não entra 
porque ao unirmos as duas forma um ciclo, enquanto uma árvore não possui ciclos, enato teremos 
aqui a aresta 𝑣5 e 𝑣6 , com peso 6, então iremos unir, não forma um ciclo então entra. Temos a 𝑣1 
e 𝑣6, o peso é 7, mas se unirmos as arestas 𝑣1 e 𝑣6, iremos pereceber que ira se formar um ciclo 
𝑣1 e 𝑣5 e 𝑣6, logo estas arestas 𝑣1 e 𝑣6 não entram na nossa árvore. Dando a continuidade ao 
algoritmo, 𝑣2 e 𝑣5, ao unirmos não formara nenhum ciclo então temos aqui uma resta que entra na 
nossa árvore geradora. Temos a 𝑣2 e 𝑣6, se formos a unir teremos o ciclo 𝑣2 e 𝑣6 e 𝑣5 , como o 
nosso objectivo é sempre evitar os ciclos não entra na nossa arvore geradora. E por fim temos a 𝑣1 
𝑉6 
𝑉1 
 
𝑉4 
 
𝑉3 
 
𝑉5 
 
𝑉2 
 
6 
 
e 𝑣4, se formos a unir 𝑣1 e 𝑣4, iremos se aperceber que temos um ciclo, este ciclo seria 𝑣1 , 𝑣5, 𝑣2 
, 𝑣3 , 𝑣4 , então não estará incluída na nossa arvore geradora. 
Resumindo: a nossa árvore geradora mínima será constituída pela aresta 𝑣2 e 𝑣3, 𝑣3 e 𝑣4, 𝑣1 e 𝑣5, 
𝑣5 e 𝑣6, 𝑣2 e 𝑣5, e terminou por tanto se formos a redesenhar a nossa aresta ou a nossa árvore 
geradora mínima, teremos o seguinte grafo: 
 
 
 3 
 
 
 4 4 
 7 
 6 
 
 
Esta é uma árvore abrangente, pois abrange todos os vértices e além disso possui, se formos a 
somar todos os valores vamos ter um custo mínimo possível desta árvore geradora: 
Custo mínimo = 6+4+7+3+4 = 24 
 
2.1.2. Algoritmo de Prim 
O algoritmo de Prim é usado para encontrar uma árvore geradora de custo mínimo em um grafo 
dado como 𝐺. A árvore geradora de um grafo 𝐺 é um subgrafo de 𝐺 formado pelo menor número 
de arestas que mantém o subgrafo ainda conexo. Já, a árvore geradora de custo mínimo é formada 
pelas arestas que, somando seus pesos, dará o menor custo total. 
𝑉6 
𝑉1 
 
𝑉4 
 
𝑉3 
 
𝑉5 
 
𝑉2 
 
7 
 
Pretende –se determinar a árvore geradora de custo mínimo ou seja a árvore abrangente, que tem 
um custo mínimo para este grafo, sabemos que a arvore abrangente é uma árvore que deve conter 
exatamente todos os vértices do nosso grafo, então temos aqui um grafo, temos aqui um grafo 
pesado, um grafo ponderado porque cada aresta está associada a um certo valor, que podemos 
chamar de peso ou custo, para o nosso grafo, aplicamos o Algoritmo de Prim, que iremos usar para 
determinar a árvore geradora mínima. 
 
 
 
 
 10 3 14 
 
 
 11 9 
 
 20 4 2 11 
 
9 
 
 
 7 5 
 
Passo 1: Consiste basicamente em escolher um vértice qualquer, escolheremos de preferência o 
vértice C, temos aqui o vértice C que é o meu vértice escolhido para analisar, então no vértice C, 
iremos analisar todas as arestas incidentes a este vértice, temos: aresta que liga C e A, aresta que 
liga C e B, aresta que liga C e G, aresta que liga C e F, aresta que liga C e E., e aresta que liga C e 
D. Dentre todas essas arestas, iremos analisar qual é a aresta que tem o menor custo ou peso, a 
aresta com menor peso é a aresta que liga C e G, por tanto o G, será o meu próximo vértice a 
analisar então temos o vértice C, G e estes dois vértices irão formar uma aresta que é CG, que fara 
A 
D 
E 
F 
B 
G 
C 
8 
 
parte da nossa árvore geradora mínima que procuramos. Feito isso passamos a ter dois vértices C 
e G para analisar, então iremos escrever todas arestas incidentes ao vértice G, que temos aresta F 
e G, e aresta G e B, então iremos analisar considerando as duas arestas C e G, iremos analisar qual 
é a aresta incidente de custo mínimo, bom analisando a aresta C, percebemos que temos aqui custo 
9, 4, 11 e 3. Analisando a aresta G, , percebemos que temos um custo 5 e 11, então percebemos 
que a próxima aresta que tem um custo mínimo e a aresta que liga C e A, por tanto iremos aqui, 
incluir a aresta C e A, como a minha próxima aresta que faz parte da árvore que estamos a montar, 
que é a árvore geradora de custo mínimo, daí passaremos a ter duas arestas que são arestas C,G e 
arestas C,A, passamos desse modo a ter 3 vértices a analisar que são C,G e A, por tanto dentre 
essas 3 arestas, temos que procurar aquela que tem um custo mínimo aresta G (5,11), aresta C 
(9,11, 9,4), aresta A (14,10), fazendo uma análise breve é mais viável a aresta C e E que tem o 
mínimo custo possível que é 4 que é incidente a aresta C, que é uma das arestas que estamos a 
analisar, por tanto a aresta C e E, fara parte da nossa árvore geradora mínima. Iremos adicionar 
um novo vértice que é o vértice E, e escrevemos junto com os vértices que já analisamos, os nossos 
vértices a analisar são C,G,A,E, temos que ver qual é a aresta que tem custo mínimo, é a aresta G 
e F, cujo o custo mínimo é 5, vamos adicionar ao nosso conjunto de vértices. Continuando vamos 
analisar destas arestas que estão em preto qual é que tem ligação com estes vértices e que tenha 
custo mínimo, temos que prestar atenção que é notório que diríamos que a próxima aresta que tem 
o custo mínimo será a aresta E e F, com peso 7, porem se formos a unir as arestas E e F, iremos 
perceber que haverá aqui um ciclo (um caminho fechado, um circuito) uma vez que a arvore 
geradora mínima ou uma arvore em teoria de grafos não possui ciclos, por tanto temos que evitar, 
esta aresta não será adicionada a nossa solução, está fora de questão, vamos procurar a próxima 
possiblidade, logicamente seria a aresta C e B, cujo o peso é 9, porque outras arestas tem um custo 
maior que 9, logo entra na nossa arvore geradora mínima, ela não forma um ciclo então é válida. 
Nos nossos vértices iremos acrescentar a letra B que é o próximo vértice e passamos a ter os vértice 
C,G,A,E,F, B e passamos a ter mais uma aresta. 
NB: Temos arestas em preto que ainda não foram preenchidas, são arestas incidentes aos vértices 
achados, iremos analisar qual é a aresta com menor custo, E e F, já analisamos está fora de questão, 
C e B, já usamos, a próxima probabilidade seria a aresta A e D, não forma um ciclo então podemos 
adicionar a nossa arvore e ficamos com mais uma aresta que inclui a aresta D. Terminado, como a 
arvore geradora mínima abrange todos os vértices do nosso grafo, nós iremos perceber que já 
9 
 
conseguimos, todos os grafos estão abrangidos pela arvore então temos, esta arvore, que é a arvore 
geradora do custo mínimo podemos redesenhar a arvore a parte: o custo mínimo é a soma de todos 
os pesos das arestas presentes na arvore geradora. 
Vertice Aresta 
C 
C,G C,G 
C,G,A CG , CA 
C,G,A,E CG, CA, CE 
C,G,A,E,F CG, CA,CE, GF 
C,G,A,E,F,B CG,CA,CE,GF, CB 
C,G,A,E,F,B,D CG, CA,CE,GF,CB,AD 
 
 
 
 
 10 3 
 
 
 9 
 
 4 2 
 
 
 
 
 5 
 
Custo mínimo = 10 + 3 + 9 + 4 + 2 + 5 = 33 
 
 
A 
D 
E 
F 
B 
G 
C 
10 
 
3. Problema do caminho mais curto 
O Problema do caminho mínimo determina o caminho mais curto entre um destino e uma origem 
em uma rede de transporte. Outras situações podem ser representadas pelo mesmo problema, como 
ilustrado pelos seguintes exemplos de aplicação. 
Exemplo: Reposição de equipamento A RentCar está desenvolvendo uma política de reposição 
para sua frota de carros considerando uma projecção de planeamento de quatro anos. No início de 
cada ano é tomada uma decisão sobre a conservação em operação ou reposição de um carro. 
Um carro deve permanecer em serviço por no mínimo um anoe no máximo três anos. A tabela a 
seguir dá o custo de reposição como uma função do ano em que o carro foi adquirido e do número 
de anos em operação. 
 
11 
 
O problema pode ser formulado como uma rede na qual os nós 1 a 5 representam o início dos anos 
1 a 5. Os arcos provenientes do nó 1 (ano 1) podem chegar somente aos nós 2, 3 e 4 porque um 
carro deve estar em operação entre 1 e 3 anos. Os arcos que vêm dos outros nós podem ser 
interpretados de maneira semelhante. O comprimento de cada arco é igual ao custo de reposição. 
A solução do problema equivale a achar o caminho mais curto entre 1 e 5. A figura acima mostra 
a rede resultante. O caminho mínimo (representado pelas linhas grossas) é 1  3  5. A solução 
significa que um carro adquirido no início do ano 1 (nó 1) deve ser substituído após dois anos, no 
início do ano 3 (nó 3). Portanto, o carro novo será mantido em serviço até o final do ano 4. O custo 
total dessa política de reposição é 12.500,00 (= 5.400,00 + 7.100,00). 
 
3.1.Algoritmos para a resolução de caminho mínimo 
Esta unidade apresenta dois algoritmos para resolver redes cíclicas (que contém ciclos, ou laços) 
e redes acíclicas: 
1. O algoritmo de Dijkstra 
2. O algoritmo de Floyd 
O algoritmo de Dijlkstra foi desenvolvido para determinar o caminho mais curto entre o nó de 
origem e qualquer outro nó da rede. O algoritmo de Floyd é mais abrangente porque permite a 
determinação do caminho mais curto entre quaisquer dois nós da rede. 
3.1.1. Algoritmo de Dijkstra 
O algoritmo de Dijkstra encontra o menor caminho de um nó fonte ou origem 𝑠 até os outros nós 
de uma rede orientada para o caso em que todos os pesos dos arcos sejam não negativos, dividindo 
os nós em dois grupos: rotulados permanentes e rotulados temporários. A distância rotulada dos 
nós permanentes representa a menor distância do nó fonte até um outro nó. No caso dos nós 
temporários, esta distância demonstra o limite superior da distância do caminho mais curto até o 
nó. Assim, em cada iteração o rótulo do nó 𝑖 é o menor caminho desde o nó fonte ao longo de um 
caminho que contém outros nós intermediários. 
12 
 
Algoritmo de Dijkstra. Seja 𝑢𝑖 a distância mais curta do nó de origem 1 ao nó i, e defina-se 𝑑𝑖𝑗 
(≥0) como o comprimento do arco (i, j). Então o algoritmo define o rótulo (etiqueta) para um nó 
imediatamente posterior, j, como: [𝑢𝑖, j] = [𝑢𝑖 + 𝑑𝑖𝑗, i], 𝑑𝑖𝑗 > 0. O rótulo para o nó inicial é [0,], 
o que indica que o nó não tem nenhum predecessor. 
 [𝑢𝑖, j] = [𝑢𝑖 + 𝑑𝑖𝑗, i], 𝑑𝑖𝑗 ≥ 0. 
O rótulo para o nó inicial é [0,], o que indica que o nó não tem nenhum predecessor. 
Os rótulos dos nós no algoritmo de Dijkstra são de dois tipos: temporários e permanentes. Um 
rótulo temporário é modificado se for possível encontrar uma rota mais curta até um nó. Se for 
possível encontrar uma rota melhor, o status do rótulo temporário muda para permanente. 
Etapa 0. Rotule o nó de origem (nó 1) com o rótulo permanente [0,]. Determine i = 1. Etapa i. 
a) Calcule os rótulos temporários [ui + dij, i] para cada nó j que puder ser alcançado partindo 
do i, contanto que j não seja permanentemente rotulado. Se o j já estiver rotulado com [uj 
, k] passando por um outro nó k, se ui + dij < uj , substitua [uj , k] por [ui + dij, i]. 
b) Se todos nós tiverem rótulos permanentes, pare. Caso contrário, seleccione o rótulo [ui , s], 
cuja distância (= ur) é a mais curta entre todos os rótulos temporários (empates são 
resolvidos arbitrariamente). Determine i = s e repita a etapa i. 
Exemplo. A rede a baixo dá as rotas possíveis e seus comprimentos em milhas entre a Cidade 1 
(nó 1) e quatro outras cidades (nós 2 a 5). Determine os caminhos mais curtos entre a Cidade 1 e 
cada uma das outras quatro cidades. 
 
Iteração 0. Designe o rótulo permanente [0,] ao nó 1. 
13 
 
Iteração 1. Os nós 2 e 3 podem ser alcançados com base no nó 1 (último nó rotulado 
permanentemente). Assim, a lista de nós rotulados (temporários e permanentes) fica como 
demonstrado na tabela a seguir: 
Lista de nós 
 
 
 
 
Para os dois rótulos temporários [100, 1] e [30, 1], o nó 3 resulta na menor distância (u3 = 30). 
Assim, o estado do nó 3 muda para permanente. 
Iteração 2. Os nós 4 e 5 podem ser alcançados com base no nó 3, a lista de nós fica como 
demonstrado na tabela a seguir: 
Lista de nós 
No Rotulo Estado 
1 [0,] Permanente 
2 [0 + 100, 1] = [100, 1] Temporário 
3 [0 + 30, 1] = [30, 1] Permanente 
4 [30 + 10, 3] = [40, 3] Temporário 
5 [30 + 60, 3] = [90, 3] Temporário 
 
O estado do rótulo [40, 3] no nó 4 muda para permanente (u4 = 40). 
Iteração 3. Nós 2 e 5 podem ser alcançados com base no nó 4. Assim, a lista de nós rotulados é 
actualizada como demonstrado na tabela a seguir: 
 
No Rotulo Estado 
1 [0,] Permanente 
2 [0 + 100, 1] = [100, 1] Temporário 
3 [0 + 30, 1] = [30, 1] Temporário 
14 
 
Lista de nós 
No Rotulo Estado 
1 [0,] Permanente 
2 [40 + 15, 4] = [55, 4] Temporário 
3 [30, 1] Permanente 
4 [40, 3] Permanente 
5 [90, 3] ou [40 + 50, 4] = [90, 
4] 
Temporário 
 
O rótulo temporário do nó 2 [100, 1] obtido na iteração 1 muda para [55, 4] na iteração 3 a fim de 
indicar que foi encontrada uma rota mais curta que passa pelo nó 4. Além disso, na iteração 3, o 
nó 5 têm dois rótulos alternativos com a mesma distância u5 = 90. 
Procedimento de rotulagem do algoritmo de Dijkstra 
 
A lista para a iteração 3 mostra que o rótulo para o nó 2 agora é permanente. Iteração 4. Só o nó 3 
pode ser alcançado com base nó 2. Contudo, o nó 3 tem um rótulo permanente e não pode ser 
rotulado novamente. A nova lista de rótulos permanece a mesma da iteração 3, excepto que o 
rótulo no nó 2 agora é permanente. Isso deixa o nó 5 com o único rótulo temporário. Como o nó 5 
não leva a outros nós, seu status é convertido em permanente, e o processo termina. Os cálculos 
do algoritmo podem ser executados com mais facilidade na rede, como a figura acima mostra. O 
15 
 
caminho mais curto entre o nó 1 e qualquer outro nó da rede é determinado começando no nó de 
destino e percorrendo a rota inversa a partir desse ponto, usando a informação dada pelos rótulos 
permanentes. Por exemplo, a seguinte sequência determina a rota mais curta do nó 1 ao nó 2. 
(2)  [55, 4]  (4)  [40, 3]  (3)  [30, 1]  (1) 
Assim, a rota desejada é 1  3  4  2 com um comprimento total de 55 milhas. 
 
3.1.2. Algoritmo de Floyd 
O algoritmo de Floyd é mais geral do que o algoritmo de Dijkstra porque determina o caminho 
mínimo entre quaisquer dois nós da rede. O algoritmo representa uma rede de n nós como uma 
matriz quadrada com n linhas e n colunas. A entrada (i, j) da matriz dá a distância, dij, do nó i ao 
nó j, que é finita se i estiver ligado directamente a j; caso contrário, é infinita. O conceito do 
algoritmo de Floyd é objectivo. Dados três nós, i, j e k, como se vê na figura a baixo, com as 
distâncias que os conectam mostradas nos três arcos, o caminho mais curto é ir de i a j passando 
por k. 
 dik + dkj < dij 
Exemplo: 
 
 
Determinar a rede mais curta. Iteração 0. As matrizes D0 e S0 dão a representação inicial da rede. 
D0 é simétrica, excepto por d53 = , porque nenhum tráfego do nó 5 ao nó 3. 
16 
 
 
Iteração 1. Determine k = 1. A linha pivô e a coluna pivô são mostradas pela primeira linha e pela 
primeira coluna sombreadas em tom mais claro na matriz D0. As células mais 
Sombreadas em tom mais escuro, d23 e d32, são as únicas que podem ser melhoradas pela 
operação tripla. Assim, D1 e S1 são obtidas de D0 e S0 da seguinte maneira: 
1. Substitua d23 por d21 + d13 = 3 + 10 = 13 e determine s23. 
2. Substitua d32 por d31 + d12 = 10 + 3 = 13 e determine s32. 
17 
 
 
Iteração 2. Determine k = 2, como mostram a linha e a coluna sombreadas em tom mais claro em 
D1. A operação tripla é aplicada às células sombreadas em tom mais escuro em D1 e S1. As 
mudanças resultantessão representadas em negrito em D2 e S2. 
 
 
 
18 
 
Iteração 3. Determine k = 3, como mostram a linha e a coluna sombreadas em D2. As novas 
matrizes são dadas por D3 e S3. 
 
Iteração 4. Determine k = 4, como mostram a linha e a coluna sombreadas em D3. As novas 
matrizes são dadas por D4 e S4. 
 
 
 
 
 
 
 
19 
 
 
 
Iteração 5. Determine k = 5, como mostram a linha e a coluna sombreadas em D4. Nenhuma 
melhoria adicional é possível nesta iteração. 
As matrizes D4 e S4 contém todas as informações necessárias para determinar a rota mais curta 
entre quaisquer dois nós da rede. Por exemplo, partindo de D4 a distância mais curta do nó 1 ao 
nó 5 é d15 = 12 milhas. Para determinar a rota associada, lembre-se de que um segmento [i, j] 
representa uma conexão directa só se dij = j. Caso contrário, i e j são conectados por pelo menos 
um outro nó intermediário. Como s15 = 4  5, a rota é dada inicialmente como 1  4  5. Agora 
como s14 = 2  4, o segmento (1, 4) não é uma conexão directa e 1  4 é substituída por 1  2 
 4, e a rota 1  4  5 agora se torna 1  2  4  5. Em seguida, como s12 = 2 e s24 = 4 e 
s45 = 5, ‘dissecção’ é necessária e 1  2  4  5 define a rota mais curta. 
 
20 
 
4. Conclusão 
Chegado ao final deste trabalho conclui – se que O problema da árvore de expansão mínima guarda 
algumas similaridades com a versão principal do problema do caminho mais curto apresentado na 
seção anterior. Em ambos os casos, uma rede conectada e não-direcionada está sendo considerada, 
em que entre as informações dadas temos alguma medida do comprimento positivo (distância, 
custo, tempo etc.) associada a cada ligação. Ambos os problemas envolvem escolher um conjunto 
de ligações que possua o comprimento total mais curto entre todos os conjuntos de ligações que 
satisfaçam determinada propriedade. Para o problema do caminho mais curto, essa propriedade é 
que as ligações escolhidas devem fornecer um caminho entre a origem e o destino. Para o problema 
da árvore de expansão mínima, a propriedade necessária é que as ligações escolhidas tenham de 
fornecer um caminho entre cada par de nós. O problema de Árvores Geradoras Mínimas também 
conhecida como “Árvore Geradora de Custo Mínimo” possui várias aplicações na atualidade, 
como por exemplo, projeto de redes de telecomunicação, fibra-ótica, redes de telefonia, projeto de 
rodovias, ferrovias, entre outros. Essas aplicações consistem na construção de grafos e resolução 
com algoritmos, como o Algoritmo de Prim e o Algoritmo de Kruskal. 
5. Referências Bibliográficas 
Colin, E. C. (2007). Pesquisa Operacional: 170 aplicações em estratégia, finanças, logística, 
produção. Rio de Janeiro: LCT. 
Hillier, F. S., & Lieberman, G. J. (2006). Introdução á Pesquisa Operacional (8ª e.d.). São Paulo: 
McGraw - Hill. 
Hillier, F. S., & Lieberman, G. J. (2013). Introdução à Pesquisa Operacional (9ª e.d.). Porto 
Alegre: AMGH. 
Taha, H. A. (2010). Pesquisa Operacional: uma visão geral (91ª e.d.). São Paulo: Pearson Prentice 
Hall.