segunda-feira, junho 05, 2006

 

Distância ponto-nó numa rede


Represente-se por d (f - (r, s), j) o comprimento do caminho mais curto do ponto f do arco (r, s) ao nó j. Esta é a chamada distância ponto-nó. Se o arco (r, s) não tem direcção, i.e., permite movimentações em ambas as direcções, esta distância deve ser a menor das duas distâncias seguintes:

a) a distância do ponto f ao nó r mais a distância do nó r ao nó j;

b) a distância do ponto f ao nó s mais a distância do nó s ao nó j.

Então,

d (f - (r, s), j) = min {f a (r, s) + d (r, j), (1 – f) a (r, s) + d (s, j)} (1a)

Se (r, s) é um arco direccionado, i.e., só são permitidas movimentações de r para s, o primeiro termo da minimização acima é eliminado e

d (f - (r, s), j) = (1 – f) a (r, s) + d (s, j) (1b)

Observe-se que só os comprimentos dos arcos e a matriz de D são necessários para calcular todas as distâncias ponto-nó.

Quando traçada em função de f, a distância ponto-nó para um dado arco (r, s) e um dado nó j toma uma das três formas mostradas na Figura 1. Note-se que o declive desta curva linear quebrada é ou + a (r, s) ou – a (r, s) e declive faz na máximo uma mudança de + a (r, s) para – a (r, s).




Figura 1. Gráficos de distâncias ponto-nó.


EVANS, James R.; MINIEKA, Edward - Optimization Algorithms For Networks and Graphs. 2.ª ed., Nova Iorque, Marcel Dekker, 1992.

Comments: Enviar um comentário

Links to this post:

Criar uma hiperligação



<< Home

This page is powered by Blogger. Isn't yours?