Não tenho!

3. PROBLEMA DE LOCALIZAÇÃO DE FACILIDADES

3.1 Introdução
Os problemas de localização de facilidades, tem como objetivo, a localização de facilidades ao longo de um sistema viário definido por um grafo, e estão divididos em 2 subproblemas conhecidos na literatura como, problema dos centros e problema das medianas.

Para dimencionar serviços de facilidades ao longo de um sistema viário é necessário a obtenção de caminhos mínimos entre os nós da rede e a localização adequada ao serviço. Para obtenção da solução de problemas desta natureza, os algoritmos mais utilizados são descritos a seguir. As definições básicas sobre Teoria dos Grafos podem ser encontradas no Anexo 1.
3.2 Algoritmos de Busca de Caminhos Mínimos em Grafos
Existem diversos algoritmos disponíveis na literatura para obtenção de caminhos mínimos entre pares de nós de um grafo, entre os quais pode-se destacar, o algoritmo de Dijkstra e o algoritmo de Floyd, apresentados nas seções subsequentes.

3.2.1 Algoritmo de Dijkstra

O algoritmo de Dijkstra foi desenvolvido originalmente para grafos finitos com custos não-negativos, podendo ser transformado para trabalhar com custas negativos, caso em que diminui sua eficiência.

O algoritmo consiste em expandir nós (gerar seus sucessores) começando pelo nó inicial, selecionando sempre aqueles ainda não escolhidos e que tiver o menor custo acumulado desde a origem.

Este algoritmo termina ao se atingir um nó terminal ou quando não existir nós para serem expandidos. Nesta última hipótese o algoritmo fracassa (COLVARA, in LAPOLLI, 1988).

3.2.2 Algoritmos de Floyd

Este algoritmo está baseado na modificação iterativa de matrizes formadas a partir da matriz de custo associada a um grafo, na qual se indicam custos infinitos para os arcos inexistentes e custo zero para os laços. Cada matriz gerada possui custos menores ou no máximo iguais aos seus correspondentes anteriores. Sendo assim, o algoritmo pesquisa novos caminhos, comparando-os com