Análise de Algoritmos para Caminhos Mínimos em Grafos

Prévia do material em texto

ANALISE DE ALGORITMOS PARA DETERMINAÇÃO DE 
CAMINHOS MINIMOS ENTRE TODOS OS P W S DE 
NÕS DE UM W F O ORIENTADO 
C a r l o s A l b e r t o da S i l v a Franco 
TESE SUBMETIDA AO CORPO DOCENTE DA COORDENAÇÃO DOS PROGRAMAS DE pós-GRADUAÇÃO 
DE ENGENHARIA DA UNIVERSIDADE FEDERAL DO R I O DE JANEIRO COMO PARTE DOS REQUI- 
S I T O S NECESSARIOS PARA A OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIA (M. Sc. ) 
A p r o v a d a por : 
/ P r e s i d e n t e H' 
R I O DE JANEIRO 
ESTADO DO R I O DE JANEIRO - BRASIL 
JUMHO D.E 1975 
A G R A D E C I M E N T O S 
De forma e s p e c i a l a Nelson Naculan F i l h o p e l a conf iança em que 
minha atuação s e j a Ú t i l ao Programa de Sistemas e também por s eu cons tan te i n - 
cen t ivo . 
A ~ o ã o Lizardo, não s ó po r admi t i r s e r o r e s p o n s ~ v e l p e l o de - 
senvolvimento d e s t e t r a b a l h o menor, mas também por s e r o modêlo de capacidade 
que todos nós, seus a lunos , procuramos a lcançar . 
A Paulo Boaventura p o r t e r concordado, em c i r c u n s t ~ n c i a s espe - 
c í a i s , e m f a z e r par te , :da banca examinadora. 
iii 
S U M A R I O 
A presen te exposiGão t r a t a do problema de determinasão do me- 
nor caminho e n t r e cada par de v é r t i c é s de um grafo or ien tado . 
Primeiramente s ão d i s c u t i d o s e comparados os t ra tamentos que 
d iversos a u t o r e s dão aos procedimentos considerados mais e f i c i e n t e s p a r a a 
solução daquele problema. - 
Em seguida do i s processos são ana l izados com maior d e t a l h e e 
é proposta em um d e l e s , uma modificaGão que r e s u l t a em uma diminuição s i g n i - 
f i c a t i v a do e s fo rço computacional. 
são apresentadas l i s t a g e n s dos programas e s c r i t o s p a r a cada 
processo, bem como pa ra a s modificações d i s c u t i d a s , anexando-se a inda os r e - 
su l t ados d a v e r i f i c a ç ã o experimental . 
The present worlc i s concerned wi th t h e problem of de te rmining 
the s h o r t e s t pa th between each p a i r of modes i n a d i r e c t e d grpph. A t f i r s t 
we d iscuss and compare the approaches followed by severa1 au thors t o t he 
procedures considered t o be the moçt e f f i c i e n t f o r t h e s o l u t i o n o£ t h a t 
problem. 
FJe then proceed t o ana lyse two procedures i n g r e a t e r d e t a i l ; 
f o r one o£ them we propose a modi f ica t ion t h a t s i g n i f i c a n t l y decreases compu - 
t a t i o n a l e f f o r t . Program l i s t i n g s a r e o f f e red f o r th.e procedures and modif i - 
c a t i o n s d iscussed , a s w e l l as t h e r e s u l t s of experimental v e r i f i c a t i o n . 
CAPÍTULO I 
1. ~ n t r o d u ~ ã o 
2. Pre l iminares 
CAPÍTULO 11 
1. introdução 
2. ~~Úmero de operaGões do Procedimento de Ployd 
3. Tratamento computacional do Procedimento 
4. ~ o n c l u s Õ e s 
CAPÍTULO 111 
1. 1n tradução 
2. ~Úmero de operaSÕes no procedimento de ~ i j l c s t r a 
3 . Tratamento computacional do procedimento 
CAPÍTULO IV 
1. ~ e r a ~ ã o d e Grafos 
2. ~ b t e n ~ ã o de tempos 
3. ~ x t e n s õ e s 
APÊNDICE I 
A - FLOYD (IBM-1130) 
B - FLOYD (B-6700) 
C - F.E.L.C.C. (IBM-1130) 
D - F.E.L.C.C. (B-6700) 
E - F.E.L.C.D. (IBM-1130) 
P - F.E.L.C.D. (B-6700) 
G - P.E.L.C.V. (IBM-1130) 
H - F.E.L.C.V. (B-6700) 
APÊLJICE 11 
A - Dijkstra (IBM-1130) 
R - Dijkstra (B-6700) 
C A P Í T U L O I 
O problema de determinação de caminhos mínimos em g r a f o s , tem 
s ido extensamente abordado em l i v r o s e a r t i g o s sobre t e o r i a de g ra fos , a p l i - 
cações de grafos , pesquisa operac iona l , e t c . Nas r e f e r ê n c i a s consul tadas pa - 
r a execução d e s t e t r aba lho , duas l i n h a s de procedimento foram claramente ob - 
sewadas : uma é a que s e ao estabelecimento d e pxovas formais p a r a o s 
d iversos métodos de busca e apresentam, eventualmente, indicações mais ou me 
nos p r e c i s a s sobre a forma computacional dos métodos. A ou t r a , mais o b j e t i - 
v a , apresenta (algumas vezes em v i r t u d e de observação das provas fo rma i s )d i s - 
cussões informais sobre os métodos e desc r i ção , na maior p a r t e das vezes com 
p l e t a mas nem sempre c o r r e t a , dos passos dos a lgor i tmos pro je tados pa ra r e so - 
lução daquele problema e , muitas vezes , o algori tmo completo já programado 
em uma linguagem de a l t o n í v e l . 
A i d é i a o r i g i n a l que ocasionou a p r e s e n t e apresentação, sur - 
g iu da observação de um t r aba lho de Minieka 1 l 2 1 , que s e enquadra no segun - 
do grupo d e s c r i t o acima. 
A s s i m , todo o desenvolvimento que s e segue, tem aspec to emi - 
nentemente p r á t i c o quando examina métodos de busca p ro j e t ados para problemas 
p a r t i c u l a r e s , métodos e s ses com provas formais em uma ou mais das r e f e r ê n c i 
a s apresentadas . O t r aba lho de Hinieka 1 l 2 1 , ap resen ta do i s a lgor i tmos pa 
ra determinação dos K menores caminhos e n t r e cada p a r de v é r t i c e s d e um g r a 
f o or ien tado , com arcos de comprimento p o s i t i v o e/ou negat ivo . O s d o i s p r c 
cessos propostos no r e f e r i d o t r aba lho são de dois a lgor i tmos 
proje tados para deter&nação do menor camiriho e n t r e cada par de v é r t i c e s de 
um grafo o r i en t ado com arcos de c u s t o p o s i t i v o e lou negat ivo . 
Como os procedimentos propostos naquele t r aba lho são gene ra 
l izaçÕes d e ou t ros , dos qua is d i z o a u t o r serem correntemente considerados 
como os mais e f i c i e n t e s pa ra reso luGão do problema de determinação do menor 
caminho e n t r e todos os pa re s de v é r t i c e s , procurou-se (com base nessa a s s e r - 
v a t i v a ) determinar s e e r a p o s s í v e l , pa ra e s t e problema: 
a ) a c e l e r a r os r e f e r i d o métodos, ou 
b) p r o j e t a r ,um algori tmo mais e f i c i e n t e . 
Assim, o~desenvolv imento d e s t e t r aba lho tem como segunda ca - 
r a c t e r í s t i c a , o t ra tamento do problema de determinação do menor caminho en - 
t r e todos os pa re s d e v é r t i c e s de um g ra fo o r i en t ado . No es tudo das r e f e - 
r ênc i a s d i sponIve i s , t r a t ando desse problema algumas conclusÕes in t e re s san - 
t e s são ob t idas e r e l a t a d a s na seção seguin te . 
2 . Pre l iminares 
P a r a reso lução do problema de determinação do caminho mínimo 
e n t r e cada par . .de . v é r t i c e s de um g ra fo o r i en t ado , d o i s t i p o s de processos 
podem s e r i den t i£ i cados : 
I - os pro je tados especif icamente para e s t e t i p o de problema 
e 
11- os pro je tados para determinar o menor caminho e n t r e um 
p a r de v é r t i c e s e que ap l icados uma vez 2 cada p a r do 
grafo , resolvem o mesmo problema. 
~ l é m d i s s o , e s s e s processos podem envolver o t ra tamento d e es- 
t r u t u r a d e á rvore , métodos i t e r a t i v o s ou m a t r i c i a i s (produto de ma t r i ze s ) . 
Os processos mais e f i c i e n t e s do t i p o I são o de Floyd 1 1, o 
d e Dantzig (ambos d i s c u t i d o s em Dreyfus 1 1 e nos qua i s s e b a s e i a o t r a b a - 
l h o de Minieka 1 l 2 I), o de Bi lde and Krarup I ' I (desenvolvido como aper - 
feigoamento do processo d e Farbey, Landand Murchland 1 1 ) e o chamado 
"Revised Cascade Method" (RCM) apresentado por Elmaghraby I ' I. Destes , o 
d e Dantzig e os das r e f e rênc ia s 1 1 , I I e 1 1 são métodos i t e r a t i v o s e 
o de 1 1 é apresentado como r e s u l t a d o de operaGÕes de produto m a t r i c i a 1 , f e i - 
t o seguado r e g r a s p a r t i c u l a r e s . 
Do t i p o LI os processos mais e f i c i e n t e s são o de I h i t i n g and 
2 4 H i l l i e r 1 1 e o de D i j k s t r a (como ana l i sado nas r e f e r ê n c i a s I 1 , I I e 
a / l 0 I ) , ambos apresentados or ig ina lmente como processos d e busca em a rvo re . 
Do exame dessas r e f e r ê n c i a s , observa-se primeiramente que t o - 
das apresentam algokitmos p ro j e t ados p a r a determinar o comprimento (ou cus to ) 
dos menores caminhos e não os caminhos em s i ( i s t o é: uma sequência ordenada 
d e nós in te rmediár ios e n t r e um nÕ origem e um nó t e rmina l ) ; embora os cami - 
nhos possam s e r ob t idos t r i b i a l m e n t e em todos os processos , i s t o ex ige sempre 
pequenas modif icaçÕes nos mesmos. Assim, mantendo-se ao lado d e s t a posiSão 
g e r a l , o desenvolvimento a s e g u i r a n a l i s a processos ( e f ina lmente uma 
modificação) que ieveriam s e r com mais r i g o r chamados de processos de de te rmi - 
nação de cus to mInimo, não s e ~ r e o c u p a n d o em d i s c u t i r o cus to computacional 
de modificações in t roduz idas para o b t e q ã o do caminho. I s t o f ina lmente s e r e - 
v e l a r á de nenhuma importância , uma vez que os do i s processos que s e r ã o compa - 
r ados , permitem a mesma modificagão (ocasionando exatamente o mesmo c u s t o com - 
pu tac iona l ) pa ra ob tengão dos caminhos. 
O segundo ponto observado, relaciona-se com a s r e f e r ê n c i a s 
I 1 , 1 1 , 1 1 e 1 1 . Floyd 1 1 apresentou em 1962, um processo pa- 
r a determinação do c u s t o mín&mo, em forma de um a lgor i tmo de nove l i n h a s es- 
c r i t o em linguagem Algol. O desconhecimento d e s t e t r a b a l h o (que s e mostrat-2 
experimentalmente no ~ a ~ í t u l o I1 s e r o mais e f i c i e n t e ) levou Farbey, Land e 
Murchland 1 1 e p u b l i c a r em 1967, um procedimento que tem alguma semelhança 
com o de Floyd, porém bem i n e f i c i e n t e s e comparado com o mesmo, uma vez que 
ex ige maior número d e comparaçÕes e ad i&es , mais memória, além de e x i g i r uma 
programasão mais complexa. Es te procedimento recebeu dos a u t o r e s o nome de 
"Cascade Algorithm". 
Tendo po r base o t r a b a l h o d e I , Bilde e Krarup I 1 , r e i - 
vindicando uma prova mais simples para a mesma i d é i a , introduzem uma modif ica - 
ção que reduz em 50% o número de "operaçoes" requer idas pa ra de te rminar uma 
ma t r i z de cus to D, onde cada d i j é o c u s t o do menor caminho do nó i ao nó j 
em um grafo o r i en t ado . Uma "operação" Dara Bi lde e Krarup é uma a p l i c a ç ã o da 
forma 
que envolve uma soma e uma comparação. 
e 
A. u t i l i z a s ã o do termo "operagao" no s e n t i d o acima, também & u 
- 
t i l i z a d a em 1 1 e 1 1 e conduz, senão 2 i-ncorregoes, pe lo menos p o s s i b i - 
l i d a d e de uma i n t e r p r e t a ç ã o imprecisa quando da comparacão e n t r e a lgor i tmos , 
tomando po r base o número de operações. Com e f e i t o , Elmaghraby 1 1 na pggi - 
na 4 de seu t r aba lho , re fere-se ao &todo d e Floyd, dizendo que o mesmo r e - 
quer n(n - 1 ) (n - 2) operasÕes elementares; mais a d i a n t e na mesma página r e f e - 
re-se ao método de D i j k s t r a dizendo que o mesmo requer 3n3 (o que em grandeza 
.- A 
j a e i nco r re to ) operacÔes .e lementares , onde uma operação elementar é uma soma 
ou uma comparaçao, consideração e s t a Última que torna i n c o r r e t a a afirmação 
sobre o número d e operações requer idas pe lo método de Floyd. 
Dreyfus 1 1 , u t i l i z a por vezes uma forma imprecisa quando £a - 
4 
l a do número de operaçÕes. Na 403 daquele t r aba lho por exemplo, e - a 
firmado que o método de Floyd requer n(n-l)(n-2) adicÕes e comparaçÕes; i s t o 
é verdade uma vez que s e cons idere a ap l icação de 1.2.1, mas é i n c o n s i s t e n t e 
- 
s e comparado com o r e s t a n t e do t r a b a l h o , quando ad ições e comparaçÕes sao 
consideradas sempre isoladamente, 
e 
O método de Bi lde e Krarup I ' I é essencialmente i g u a l ao me 
todo de Floyd e recebeu dos a u t o r e s a denominação de "Modified Cascade Algo - 
r i thm" . 
Elmaghraby 1 1 ap resen ta em 1970 o método de Floyd, com a 
denominação d e "Revised Cascade Method". Neste t r a b a l h o , como em I I e 
- 
1 1, aquele método é apresentado como requerendo n(n-1) (n-2) operaçoes. 
Essas observações sobre i n c o n s i s t e n c i a ou incor reções menores 
não são f e i t a s como t e n t a t i v a de i n v a l i d a r os t r aba lhos em que e l a s ocorrem, 
mas s i m com o o b j e t i v o de e s t abe l ece r com maior exa t idão o número d e opera - 
ções requeridas por procedimentos d i f e r e n t e s (visando um mesmo resu1tado)que 
é e m r e a l i d a d e o que o usuá r io u t i l i z a para uma tomada d e dec isão . 
No c a p í t u l o segu in t e , o método de Floyd, doravante chamado de 
"procedimento de Floyd" s e r á apresentado por completo, determinando-se o nÚ - 
mero de adições e comparações requer idas , juntamente com re su l t ados e x p e r i - 
mentais da modificação do processo segundo I ' I e / 1 , que mostrarão s e r 
a s r e f e r i d a s a ~ r e s e n t a ç õ e s i n e f i c i e n t e s quando comparadas com o t r aba lho o r i - 
g ina l 1 ti 1 . Deve-se observar que o processo de Dantzig como apresentado em 
1 1 e 1 l 2 1 requer o mesmo número de adições e cornparaçÕes que o processo 
d e Floyd, exce to p a r a casos p a r t i c u l a r e s como examinados por BrasSin 
e Minoux 1 ' 1 por exemplo (grafos não o r i en t ados e de a r cos com c u s t o s p o s i - 
t i v o s ) . porém po r e x i g i r programaCão mais compaexa, e s t e processo p r a t i c a - 
mente não é u t i l i z a d o . 
A gene ra l i zação do método de D i j k s t r a , doravante chamado "pro - 
4 
cedimento d e D i jk s t r a " , s e r á apresen tado no ~ a ~ z t u l o 111, mostrando-se o nu - 
mero de adicÕes e comparaçÕes por e l e r eque r ido e uma modificação, que toma 
por base a apresen tação f e i t a por Dreyfus 1 1 , será d i s c u t i d a com s e u s re- 
su l t ados computacionais . Na apresen tação des se s d o i s procedimentos, empre - 
- 
gar-se-: o termo "operaçao" como uma ad i ção - ou uma comparação. O motivo de 
s e f a z e r a a n á l i s e tomando por base e s s e s d o i s t i p o s de operação é p o r serem 
e l a s realmente dominantes em termos de tempo de máquina, quando comparadas 
com o u t r a s (assumindo-se uma equ iva l ênc i a e n t r e o número de operações d e i n - 
dexação nos processos comparados). O f a t o r considerado para comparação en - 
t r e procedimentosserá o tempo, embora alguma observação sob re memória s e j a 
f e i t a eventualmente. O r e s u l t a d o f ina lmente ob t ido , d i z r e s p e i t o 2 a c e l e r a - 
$20 de um procedimento que já e x i s t e . Superar a s impl ic idade e e f i c i ê n c i a 
do procedimento de Floyd p a r a o problema e m ques tão , p e l o desenvolvimento de 
um novo a lgor i tmo, revelou-se uma t a r e f a complexa o s u f i c i e n t e pa ra ser aban - 
donada em um p r ime i ro ataque, embora cont inue sendo uma p o s s i b i l i d a d e de 
algum i n t e r e s s e . 
7 
C A P Í T U L O I1 
O procedimento de Floyd, r e so lve o problema d e determinação do 
menor cus to e n t r e cada par de nós de um grafo or ien tado , com a rcos de cus to 
p o s i t i v o e/ou negat ivo . Como apresentado por I ' I, 1 1 , 1 1 e pe lo p ró - 
4 
p r i o Floyd 1 1, c i r c u i t o s de cus to negat ivo não são permit idos , porem uma 
pequena modificasão no procedimento conduz a r e s u l t a d o s c o r r e t o s em t a l caso. 
A a£ irmação cont ida em 1 1 , de que o número de operações requeridas pe lo 
- 
procedimento é n(n-l)(n-2) para o cado d i j 2 O não é p r e c i s a , uma vez que sao 
ob t idos r e s u l t a d o s c o r r e t o s com um ou mais dos d tendo v a l o r nega t ivo , e x i s i j - 
t i ndo apenas a r e s t r i ç ã o da não e x i s t ê n c i a de c i r c u i t o s . 
Pa ra um grafo o r i en t ado com n nós, cons t ró i - se uma ma t r i z de 
d i s t â n c i a s D(n x n ) com a s s egu in t e s c a r a c t e r í s t i c a s : 
b ) d.ij = C , onde c é o c u s t o associado ao a rco que une os 
nós i e j ( i # j ) 
c ) d . . = oo s e não e x i s t e a r co unindo os nós i e j . 
1- 3 
O procedimento determina o cus to do caminho mínimo . i n s e r i n d o 
4 
nos , quando apropriado, e m caminhos menores. Começando com a ma t r i z D de 
d i s t â n c i a s d i r e t a s , n mat r izes s ão cons t r u i d a s sequencialmente (em r e a l i d a d e 
as modificaçÕes s e r ã o e fe tuadas sobre a mat r iz o r i g i n a l ) . A ma t r i z de ordem 
K é i n t e r p r e t a d a como contendo os cus tos dos menores caminhos e n t r e os pares 
( i , j ) , onde apenas caminhos com nós in te rmediár ios pertencendo ao conjunto 
de nós de 1 2 K são permi t idos . A mat r i z de ordem K é constnuida da de or- 
dem (K - 1 ) p e l a u t i l i z a s ã o de : 
o 
d . . = d . . são os elementos da mat r iz d e d i s t â n c i a s d i r e t a s . K é i n i c i a l - 
1 3 1.1 
mente 1 e é incrementado de 1 depois de i e j (nes t a ordem) terem assumido va - 
lares de 1 N, a t é I< = n no f i n a l . 
Como exem?lo, é apresentado um grafo com a rcos de cus to ' p o s i t i - 
# 
vo, com c inco nos; para cada mat r iz de ordem K os elementos d modificados i j 
são indicados em separado. Um ponto i n t e r e s s a n t e é que o procedimento inde - 
pende da numeração dos nós. 
~1 = O 5 , aqui d42 = d41 + d14 
1 2 w o 1 
D2 = O 5 , aqui d I 3 = dI2 f dZ3 
aqui não houve modificaGão de nenhm elemento, donde se pode c o n c l u i r que o 
10 
nÕ d e nÜmero 3 não é i n t e rmed iá r io d e nenhum caminha. 
aqui : d15 = d14 + d45 
m o 1 a3 1 
aqui : - 
3 0 1 2 1 d 2 1 - d25 + $51 
Como K = n , interrompe-se o processo. 
0 s caminhos (P) obt idos : 
a ) a p a r t i r do nó 1 
P12 = 1 ,2 (a rco d i r e t o ) 
P13 = 1 , 2 , 3 
b) a p a r t i r do nó 2 
Psl = 2 ,5 ,4 ,1 
'23 
= 2,3 
c ) a p a r t i r do nÕ 3 
P31 = 3,5,4,1 
P32 = 3,5 ,4 ,1 ,2 
P34 = 3,5,4 
= 3,5 
d) a p a r t i r do nó 4 
= 4 , l 
P42 = 4 , 1 * 2 
P43 = 4'1,2,3 
P45 = 4,5 
e ) a p a r t í r d o nÕ 5 
P51= 5 , 4 , 1 
= 5 ,4 ,1 ,2 
P53 = 5 , 4 , 1 , 2 , 3 
= 5 , 4 
2. ~Úmero d e operações d o procedimento d e Floyd 
A a p l i c a ç ã o d a forma 2.1 .1 é f e i t a n 2 v e z e s p a r a cada K. Lem- 
s e e n t ã o , no t o t a l , n 3 apl icaçÕes que correspondem ã 2n3 operações r e a l i z a d a s 
s o b r e a m a t r i z d e c u s t o s d i r e t o s p a r a que se obtenha a m a t r i z d e c u s t o s 
mos. 
E s t e r e s u l t a d o pode ser o b t i d o por inspeGão em Ployd 1 
é a p r e s e n t a d o também p o r Xi-nieka 1 l 2 1 . Nas r e f e r ê n c i a s I ' 1, 1 1 e 
I e 
4 
1 4 1 
f a l a - s e em n(n-1) (n-2) operar,Ões, o que e menos p e c i s o . Fiais c o r r e t o seria 
d i z e r 2n(n-1) (n-2) operaFÕes, quando algumas apl icaçÔes d e 2 .1 .1 s ã o e v i t a - 
d a s , em vir tude das cons ideraçÕes s e g u i n t e s . 
Para cada K, os &lementos d a K-ési.ma l i n h a e da K-ésirna coluna 
não precisàm s e r examinados, uma vez que não podem s o f r e r a l t e r a ç ã o dado O £a - 
t o de s e r o nó I<, um nó t e rmina l em d ( i ) e o nó i n i c i a l em d ( j) ; as 
i k K j - 
sim é desnecessár io v e r i f i c a r s e e x i s t e redução do cus to p e l a in t rodução de 
um nó em um caminho onde e l e é o nó i n i c i a l ou te rmina l . Tal f a t o s ó ocor re - 
r i a caso fos se permit ido c i r c u i t o negat ivo. 
Para cada K tem-se en tão (n-1) apl icações d e 2.1.1. ~amhém em 
v i r t u d e de s e t e r condiderado d . = O i e não s e admitindo c i r c u i t o s n e g a t i ii - 
vos , os elementos d a d iagonal p r i n c i p a l não so f r e rão , em todo o processo,qual - 
quer t i p o de a l t e r a ç ã o . Po r t an to , em cada K, onde já s e e s t á fazendo apenas 
(n-1)* aplicacÕes de 2.1.1, mais (n-1) podem s e r e v i t a d a s . 
Assim, em termos de operações, o processo i n t e i r o requer : 
2n((n-i) * - [n-1) ) = 2n(n-1) (n-2) = 
2n3 - 6n2 + 4n operações (2.2.1) 
O que não é observado em I ' 1, 1 1 e 1 1 é que embora 
2.. 2.1 s e j a teoricamente c o r r e t o , e necessá r io i n t r o d u z i r um c e r t o número de 
operações do tj-po comparação e/ou indexaGão para que s e possa e v i t a r algumas 
ap l icações de 2.1.1; o número dessas operações e x t r a o r d i n á r i a s , quando cons i 
deradas no processo, a l t e r am 2.2.1. Na seção segu in t e , são apresentadas duas 
formas de introdução dessas operações e seus r e s u l t a d o s p r á t i c o s s ão apresen - 
tados. 
3. Tratamento computacional do procedimento 
A ve r são o r i g i n a l do procedimento de Floyd, requerendo 2n3 o- 
- 
peraçoes, f o i programada em linguagem FORTUN. Com base nessa programação, 
t r e s modificações foram t en tadas , visando o b t e r o r e su l t ado 2.2.1 : 
a ) in t rodução de comparações pa ra e v i t a r aplicaçÕes de 2.1.1 
aos elementos de l i n h a s e colunas. 
b ) in t rodução de comparaçÕes pa ra e v i t a r ap l icações de 2.1.1 
aos elementos de l i n h a s , colunas e d iagonal . 
c ) c r i a ç ã o de uni v e t o r a u x i l i a r para e v i t a r ap l icações de 
2.1.1 aos elementos de l i n h a s e colunas. 
A s modificaçÕes do pr imei ro t i p o d e s c r i t o acima, requerem n 3 
comparações ad i c iona i s ; a s do segundo t i p o requerem 2n3 - 2n2 + n compara - 
$Ões a d i c i o n a i s ( i s t 0 é t r i v i a lmen te obt ido por inspeção das l i s t a g e n s apre- 
sen tadas no Apendice I, p a r t e s C e D - pa ra o i tem a - e p a r t e s E e F - p 2 
r a o i tem b ) . 
Temos en tão para o procedimento de Floyd: 
3 I - o r i g i n a l (sem el iminações) = 2n operações 
I1 - evi tando l i n h a s e co lunas(por comparaqão) = 
3n3 - 6n2 + 4n operações 
111- evi tando l i n h a s , colunas e diagonal (por comparação) = 
4n3 - 8n2 + 5n operações 
O t ratamento do Último i t e m , não requer operações ad i c iona i s 
de comparação. A i d é i a é c r i a r um v e t o r de n posiçÕes ( s e j a IND o nome do 
v e t o r ) e i n i c i a l i z á - 1 0 com LhQ(N) = N. Para cada I< no procedimento, 
I N D (K) = IED ( i ) 
I N D (1) = K. 
Para va r i ação dos i e j em 2.1.1, consideram-se agora o s e l e - 
mentos ( a p a r t i r do segundo>., do v e t o r IED. Assim, todas a s l i n h a s e co1u.- 
nas e s t ã o sendo cons ideradas , exce to a s de ordem K pa ra cada K (as l i s t a g e n s 
correspondentes 2 e s t a modificação e s t ã o no ~ ~ ê n d i c e I, p a r t e s G e H) . O nÚ - 
2 mero de operações de indexaGão in t roduz idas , é de n 3 - n . 
são apresen tadas a s e g u i r , duas t a b e l a s que indicam o tempo 
g a s t o em processarnento somente para a l t e r a ç ã o da ma t r i z de d i s t â n c i a s d i r e - 
t a s a t é s e ob t e r a ma t r i z de cus to s mznimos. Como se pode n o t a r nos progra- 
- 
mas apresentados no ~ ~ ê n d i c e I, es t e tempo não envolve l e i t u r a ou impressa0 
de dados, ou chamada de qualquer t i p o de sub-programa ou s u b - ~ o t i n a . O p r o - 
d 
ces so o r i g i n a l e a s m ~ d i f i c a ~ õ e s aplicam-se sempre ao mesmo g ra fo , que e ge- 
rado pe los programas com c a r a c t e r É s t i c a s que s e r ã o v i s t a s no c a p I t u - 
10 IV. 
Nas t a b e l a s 1 e 2 dadas a s e g u i r empregou-se: 
FLOYD - procedimento de Ployd sem modificaçÕes . 
P.E.L.C.C.- procedimento de Floyd ev i tando l i n h a s e colunas 
- 
por coniparaçoes . 
F.E.L.C.D.- procedimento de Floyd ev i tando l i n h a s , colunas e 
d iagonal . 
F.E.L.C.V.- procedimento de Floyd ev i tando l i n h a s e colunas 
po r v e t o r . 
A t a b e l a 1 o r e s u l t a d o de processamentos no s i s t ema IBM- 
1130 e a t a b e l a 2, no s i s t ema B-6700. Em todos os casos a unidade de tempo 
é o segundo. 
T A B E L A 1 
~Ümero de nós FLOYD F.E.L.C.D. P.E.L.C.V. 
T A B E L A 2 
PLOYD F.E.L.C.D. F.E.L.C.V. 
f? i n t e r e s s a n t e observar que a t e n t a t i v a d a não ap l i cação de 
2.1.1 2 l i n h a s e colunas, p e l a c r i a ç ã o de um v e t o r a u x i l i a r , envolve n3 - n 2 
operações do t i p o 
que s e ap re sen t a (pa ra o scstema IBV-1130)bem p i o r que o esperado. Aqui a ' 
e x p e c t a t i v a e r a de que o r e s u l t a d o ob t ido , e s t i v e s s e d a forma 11, 
- 
i s t o porque as operaGÕes de indexação simples sao , com f r equênc i a , conside- 
radas como requerendo o mesmo tempo que as operações de comparação; e n t r e - 
t a n t o , e s t a modificação s e r e v e l a p i o r que a d a forma 111. 
Deve-se observar a inda , que as modificaçÕes sobre o processo 
o r i g i n a l , podem t e r alguma vantagem pa ra grafos de a t é um p o r t e determina - 
do. A s s i m o P.E.L.C.C. (modificação mais v a n t a j o s a ) , consome menos tempo 
para grafos com a t é 75 nós , p a r a a máquina u t i l i z a d a n a determinação d a t a - 
b e l a l , e g ra fos com aproximadamente 40 nós , pa ra 'a máquina u t i l i z a d a n a de- 
terminação d a t a b e l a 2 . 
O ponto pa ra que s e deve a t e n t a r é que e s s a "vantagem" pa ra 
g ra fos de pequeno p o r t e (com l i m i t e e m funr$o do s i s tema computacional e m - 
pregado) não é s i g n i f i c a t i v a a não s e r em casos extremos. Com e f e i t o ve ja - 
s e que no caso do s i s tema IBK-1130, p a r a o t r a b a l h o em 1000 grafos de 42 
4 . 
nos, ter iamos um ganho aproximado de 35 minutos e m 27 horas s e f o s s e u t i l i - 
zado o F.E.L.C.C. e m l u g a r de PLOYD. 
O que se t en tou mos t ra r en tão , é que e m g e r a l a forma mais e f i - 
c i e n t e (que. consome menos tempo, uma vez que a memória para. a s modif i cações 
dos pr iméi ro e segundo t i p o s é a mesma e pa ra o t e r c e i r o t i p o apenas é ne- 
c e s s á r i o mais um v e t o r de n posiçÕes) do procedimento de FLOYD é a que a p l i c a 
2.1.1 todos os elementos d a ma t r i z de d i s t â n c i a s o r i g i n a l . Assim a compara - 
ção com ou t ros procedimentos deve tomar por base o f a t o de que o procedimento 
de FLOYD requer 2n3 operações e não 2n3 - ~ n * + 4n como é usualmente apresen - 
tado. 
O procedimento de Di jks t ra f o i originalmente proposto pe lo mes- 
mo como um método de busca que permite determinar uma solução (um caminho) 
para um problema e m que se d e f i n e um es tado i n i c i a l (um nó r a i z ) e um es tado 
ob je t ivo (com um nó ob je t ivo ou mais). O mesmo processo f o i proposto Por 
Whiting and H i l l i e r '1' l7 1 sem re fe rênc ia ao t rabalho de Di jks t ra e também 
por Nilsson 1 1 com o nome de "Uniform-Cost Method". 
A apl icação do procedimento, o r ig ina uma "árvore de busca" on- 
de são u t i l i z a d o s apontadores em cada nó, para que o caminho-solução s e j a re- 
construido a t é o nó origem quando s e a t inge um nó obje t ivo . Uma p r o p o s i ç ~ o 
sobre a forma mais e f i c i e n t e de s e t rabalhar com a s e s t r u t u r a s provenientes da 
aplicação d e s t e prwédimento é f e i t a por Johnson 1 l 0 1 . Uma pequena modifica - 
ção no método o r i g i n a l permite que s e t rabalhe também em grafos orientados ou 
- 
nao. O cus to de t r ans ição e n t r e estados (valores associados aos arcos que li- 
gam os nós) pode s e r p o s i t i v o ou negativo (aqui ou t ra modificação deve 
ser f e i t a ) , porém após a pùblicação de um t rabalho de Johnson 1 1 , observa- 
s e que apenas com custos pos i t ivos são obtidos resul tados super iores outros 
processos. Johnson 1 1, quest iona a af i rmat iva de Elmaghraby 1 1 de que 
o procedimento de Di jks t ra requer 3n3 operações para resolver o problema de 
determinar os menores caminhos e n t r e um nó e todos os outros e m um grafo o r i en - 
tado, com arcos de cus to p o s i t i v o e/ou negativo; é proposta uma e s t r u t u r a com 
n .., arcos de cus to negativo e se prova que são requeridas n2 operaçoes. A s eons8 - 
derações f e i t a s a segui r , e s t a rão , por e s t e motivo r e s t r i t a s a o caso de arcos 
de custo p o s i t i v o em grafos orientados. 
Fixando um nó com r a i z e estabelecendo-se como nó ob je t ivo -ca - 
da um dos n-1 r e s t a n t e s de cada vez, a apl icação do procedimento de Di jks t ra 
n-1 vezes r e s u l t a na determinação dos menores caminhos e n t r e um nó e todos os 
out ros . Neste nzvel de generalização do procedimento observa-se que um t r a t a - 
mento i t e r a t i v o é p o s s ~ v e l e vantajoso. A forma proposta p o r Elmaghraby 1 ( 
é i n t e ressan te , mas como apresentada por Dreyfus 1 1 é mais c l a r a e bastan - 
t e simples: 
a ) a t r i b u i r ao nó r a i z o cus to zero e aos n-1 r e s t a n t e s , i n f i 
n i t o . O cus to do nó r a i z é considerado permanente . 
b) comparar o cus to de cada nó (exceto o do r a i z ) com a soma 
do cus to do nó r a i z com o cus to do arco d i r e t o do nó r a i z 
ao nó em questão. Se a soma f o r menor, s u b s t i t u i r o cus to 
presente pe lo va lo r da soma. 
c ) determinar qual o menor dos cus tos (excetuando-se os perma - 
nentes) e tomá-lo como permanenee. 
d) comparar o cus to de cada nó r e s t a n t e com a soma do cus to 
do nó f e i t o permanente no passo a n t e r i o r e o cus to do ar - 
co d i r e t o do nó permanente ao nó em questão. Se a soma 
fo r menor, s u b s t i t u i r o cus to presente pelo v a l o r da soma. 
e ) v o l t a r ao passo c e r e p e t i r os passos c e d. 
Com n-1 execuções do passo c , interrompe-se o processo. 
Para exemplif i c a r o procedimento, tome-se o graf o apresentado 
no ~ a ~ í t u l o I1 onde s e quer determinar os menores caminhos e n t r e o nó 1 e os 
4 
demais. Na representação a segu i r , um nó de cus to permanente, s e r a represen - 
tado com um t r a ç o sob o ~ u s t o . 
nós ( i ) 1 2 3 4 5 
k 
custo (dli) ' 0 - w w w w K = l 
Assim: d = 1, d13 = 2, d14 = 0.5 e d15 = 1.5 são os custos 
12 
dos caminhos mínimos. Os caminhos são obtidos na seguinte ordem: 
2. ~Úmero d e operações no procedimento de D i jkstra 
"(" - adições e 2 "(" - comparações para tenrati- 2 
va de modif icaç~o dos custos. 
n(n - 1) 
2 
cornparaçÓes para determinar qual cus to se- 
rá permanente. 
3 ~ n t ã o : - 
2 
n(n - 1 ) operações para determinar os menores 
caminhos e n t r e um nó e todos os outros. Se o processo é aplicado aos n nós, 
4 
n2 (n - 1) operações. ~ l é m d i s s o é necessá2io ind ica r os nos tem-se - 
2 
que vão tendo os custos considerados como permanentes. A forma sugerida co- 
mo e f i c i e n t e p or Dreyfus 1 1 , é assoc ia r cada nó,; um índice que v a r i a de 
zero 5 um quando o custo é tomado como permanente. Nos passos b e d a n t e r i - 
ormente d e s c r i t o s , inc lu i -se um t e s t e de ve r i f i cação do índice associado ao 
no em exame: s e o índice é zero, o processo é aplicado normalmente; s e o ín- 
d ice é um (cus to permanente), examina-se o nó seguinte. Desta forma, n(n - 1) 
4 
comparaçÕes adic ionais são necessár ias na aplicação do processo 2 cada no; 
para determinar os menores caminhos e n t r e cada pa r de n&, n2(n,-- 1) compara - 
çÕes de índ ices são por tanto necessár ias . 
O processo todo envolve então: n2(n - 1) + n2(n - 1 ) = 2 
2.5 n3 - 2.5 n2 operaç&s (3.2.1) 
~ambém n2(n - 1 ) operaSÕes de indexação são efetuadas. 
Se comparada com o procedimento de Floyd, a apresentação do 
procedimento de R i j k s t r a nessa forma é realmente menos e f i c i e n t e , jus t i f i can- 
do uma indicação negativa para e s t e Último f e i t a por Dreyfus 1 1 . A memória 
requerida pelo procedimento de ITijkstra é também maior que a requerida por 
Floyd. Mesmo que as modificaçÕes de custo sejam efetuadas diretamente sobre 
a matriz de custos d i r e t o s é necessár io um conjunto de n elementos para o t r a 
balho com os índices que indicam s e o cus to é ou não permanente em um dado 
i n s t a n t e . 
3. Tratamento computacional do procedimento 
Uma a n á l i s e no procedimento de D i j k s t r a como apresentado por 
Dreyfus 1 ] r e v e l a do i s pontos que s e convenientemente toatados devem melho - 
r a r a sua e f i c i ê n c i a . 
O primeiro ponto d i z r e s p e i t o aos passos a e b d e s c r i t o s na 
seção 2. Resulta da aplicação do passo b , que a a t r i b u i ç ã o temporária LFeita 
no passo a , i r á se reduz i r aos cus tos apresentados pela matr iz de cus tos d i r e - 
t o s . Assim é desnecessário t r a b a l h a r com um conjunto a u x i l i a r de cus tos , on- 
de são efe tuadas a s modificações; a u t i l i z a ç ã o desse comjunto de n elementos, 
juntamente com a s n posiçÕes ad ic iona i s para os índ ices que indicam s e o cus- 
t o é ou não permanente, r e s u l t a em 2n posiçÕes de memória a mais em D i j k s t r a 
com re lação a Floyd. A s modificaçÕes podem s e r f e i t a s então d i ~ t a m e n t e so- 
b re a matriz de d i s t â n c i a s , considerando-se inicialmente o cus to do nó r a i z 
- 
como permanente e eliminando-se os passos a e b d a descrição f e i t a na seçao 
1 des te ~ a p g t u l o . 
C 
O segundo ponto s e r e l ac iona com a forma de i n d i c a r qual no 
tem custo permanente pe la u t i l i zação de índices zero ou um como sugerido por 
Dreyfus 1 1 . A forma aqui proposta se revela mais e f i c i e n t e , uma vez que 
não são necessár ios n2 (n - 1) comparaçÕes de índices , a l t e rando 3.2.1 de ma- 
n e i r a s ign i f i can te . 
É formado um v e t o r IM), de n com IND(1) contendo o 
número do nó ra iz ; a cada vez que o c u s t o de um nó f o r tomado como permanen - 
t e , o seu número é deslocado para a posição seguinte ao Último elemento em 
I N D que f o i tomado como permanente. 
Desta posição de I N D , a t é IND(N) e s t ã o os números dos nós de 
cus to não permanente. 
Como exemplo, s e j a a l i n h a I d a matr iz D O do grafo apresenta- 
do no ~ a ~ T t u l o 11. O ve to r associado aquela l i n h a será : 
Com 13-2 comparações determina-se que IND(4) (que contém o nÚ- 
mero do nó 4) é o que t e m menor cus to associado, então ele é tomado como per- 
manente e f &-se com: 
Aplica-se agora d =min(dli , d + d .) para 3 < i ZN, onde p = IND(2). F i li i~ PI 
ca-se com 
o menor é IND(4) (que contêm o número de nó 2) . ~ n t ã o : 
agora d = m i n ( d d + d ) para 4 1 i Z N , onde p =IND(3). 
li li' l p p i - - 
Fica-se com 
e o menor é IND(5) (que contém o número do nó 5 ) . ~ n t ã o : 
a g o r a d = m i n ( d d + d ) p a r a i = N e p = I N D ( 4 ) . 
li li' l p p i 
Neste ponto o processo pode s e r interrompido. 
O número de operações com e s t a s duas modif icações é: 
(n - 1) (n - 2) adi.,~es e 
2 
- - 2, comparaçÕes pa ra t e n t a t i v a de 
2 
modificação dos custos. 
(n - 1) (n - 2) 
2 comparações para determinar o menor custo. 
3 C ~ n t ã o : -(n - 1) (n - 2) para determinar os menores caminhos e n t r e um no 
2 
e todos os out ros . A aplicação do procedimento aos n nós r e s u l t a e m 
1.5 n L 4.5 n2 + 3n operações (3.3.1). 
O número de operações de indexação está e$ torno de 
- - para todo o processo. Observe-se que e s t e Último nÚmero,mes 
2 - 
mo s e somado à 3.3.1, ainda r e s u l t a em um t o t a l que é i n f e r i o r aos 2n3 do 
procedimento de Floyd. 
Na tabela apresentada a segu i r , indica-se o tempo gas to em 
processamento sõmente para a l t e ração da matriz de d i s t â n c i a s d i r e t a s até s e 
obter a matr iz de custos mínimos. Êste tempo não envolve l e i t u r a ou impres- 
são de dados, ou chamada de qualquer função ou sub-rot ina ; os procedimentos 
comparados aplicam-se sempre ao mesmo grafo, que é gerado pelos p r 2 
gramas com c a r a c t e r ~ s t i c a s que se rão v i s t a s no c a p í t u l o I V . Aqui empregou-se: 
FLOYD - procedimento de Floyd modif icaGÓes. 
DIJKSTRA - procedimento d e D i jks t r a com modif icaçÕes. 
O s sitemas u t i l i z a d o s s ã o o IBM-1130 e o B-6700; a unidade de 
tempo é o segundo. O s programas e s t ã o l i s t a d o s no ~ ~ ê n d i c e I, parees A e B 
p a r a o p r ime i ro procedimento e no ~ ~ ê n d i c e 11, para o segundo procedimento. 
T A B E L A 3 
IBM - 1130 
FLOYD D I JKSTRA 
B - 6700 
FLOYD D I JKSTRA 
0.002 0.001 
o. 017 0.011 
0.058 0.041 
O. 144 0.097 
0.272 0.186 
O. 454 0.316 
O. 730 0.517 
1.055 0. 746 
1.541 1.073 
2.089 1.469 
2.805 1.923 
3.601 2.477 
4.474 3.148 
5.786 4.057 
6.974 4.897 
4. ~ o n c l u s õ e s 
Na t a b e l a 3, observa-se que a menos de uma f lu tuação nas medi- 
das f e i t a s em grafos de pequeno por te devido imprecisão dos mecanismos de 
determinação do tempo, já para quinze nós tem-se um ganho super ior v i n t e 
por cento em Di jks t ra . Para noventa nós, o ganho já e s t a bem próximo à v i n t e 
e c inco por cento e quase es t ab i l i zado . 
- 
A s modif icações propostas no procedimento de D i j k s t r a , sao re- 
almente s i g n i f i c a n t e s , embora tenha-se reduzido o campo de aplicação aos gra- 
f o s com arcos de cus to pos i t ivo . ~ l é m d i s s o a memória requerida é um pouco 
maior (mais um ve to r de n e a complexidade do programa também aumen - 
t a . 
Essas "desvantagens" em D i j k s t r a são compensadas pe lo f a t o de 
se t e r um procedimento que s e p r e s t a 3 solução de do i s problemas: 
a - determinação do menor caminho e n t r e todos os pares 
b - determinação do menor caminho e n t r e um nó e todos os ou- 
t r o s , 
e também por se poder, e m D i j k s t r a , t r aba lha r com a matriz o r i g i n a l em arqui - 
vo e em cada passo opexar com apenas uma l i n h a na memória cen t ra l . A s s i m o 
que s e f a z é resolver n problemas do t i p o b acima. Embora &se tratamento tam - 
bém possa s e r dispensado ao procedimento de Floyd, e l e é mais oneroso e m v i r 
tude de s e r necessár io t r a n s f e r i r n vezes cada l i n h a da matr iz o r i g i n a l em a r - 
quivo para a memória c e n t r a l . Para grafos de médio e grande por te a "vanta - 
gem" do procedimento de D i j k s t r a deve se acentuar ao ganho de tempo na opera- 
- 
çao com arquivos . 
1. ~ e r a ~ ã o dos Grafos 
Para comparação dos tempos gastos pelos procedimentos apresenta - 
dos nos do i s c a p í t u lo s an te r io res , o mesmo conjunto de grafos f o i gerado em 
cada programa. 
'Eohou-se o va lo r 3 como razoável pa ra o incremento n a dimensão 
dos grafos. Assim o processo é gerar um grafo de n nós ( inicialmente n toma 
4 
o v a l o r 3) e a p l i c a r o procedimento; gerar novo grafo com n + 3 nos e a p l i - 
c a r novamente o procedimento continuando-se des ta forma a t é s e esgotar o tem- 
po s o l i c i t a d o ao sis tema computacional. 
Como s e es tuda sempre o caso de grafos or ientados , é necessár io 
para cada grafo de n nós, ge ra r uma matriz D(n x n ) . Essa matriz tem tres 
t i p o s de elementos: 
I - elementos da diagonal p r i n c i p a l igua i s à zero. 
11- elementos com um va lo r igua l ao cus to do arco ligando do i s nós. 
111-elementos igua i s "infini to1 ' , o que s i g n i f i c a não haver arco l igando dois 
1 
nos. 
Para os elementos do t i p o 11, optou-se (sem nenhum motivo p a r t i - 
c u l a r ) p e l a f a i x a dos r e a i s de um 2 dez. Para os t i p o 111, & s u f i c i e n t e f a z e r 
para cada grafo, cada um des tes elementos 'tomar o va lo r ~xTf.3;~ i s t o porque ha- 
bendo no máximo n - 1 arcos ligando do i s nós e o cus to de cada arco sendo no 
máximo igua l a dez, aquele v a l o r é super ior ao cus to de qualquer caminho que 
s e venha a obter . 
Para a t r i b u i r um custo r e a l ou i n f i n i t o 2 cada arco, o processo 
C 
e : 
I .- gera r um número a l e a t ó r i o e n t r e zero e um. 
11 - se o número é i n f e r i o r 2 0.5, a t r i b u i r "inf i n i t o t f (n x 10) ao elemento em 
questão, caso c o n t r á r i o 
111- gerar números a l e a t ó r i o s a t é s e obter um igua l ou superior à 0 .I. Quando 
i s t o acontecer, mul t ip l ica- lo por dez e a t r i b u i r e s t e v a l o r ao elemento 
e m questao. 
I V - r e p e t i r a p a r t i r de I , a t é que a matr iz D(n x n) e s t e j a completa. 
A geração de a l e a t ó r i o s s e f e z no sistema B-6700 pe la chamada da 
função RANDOM. No sistema IBM-1130 f o i necessár io i n t r o d u z i r uma r o t i n a de 
geração (ver programas dos apêndices) . ~ambém para &se sis tema, embora fos- 
sem gerados números a l e a t ó r i o s e n t r e zero e um, os va lo res a t r ibu idos aos ele - 
mentes da matriz de d i s t ânc ias eram sempre intei-ros; i s t o porque o processa- 
mento de quantidades r e a i s no IBM-1130 é f e i t o por software e e s t e f a t o oca- 
s iona d i ferenças s i g n i f i can tes nos tempos obtidos em cada procedimento, além 
de aumentar em muito o tempo global de u t i l i z a ç ã o da mgquina. 
Na t a b e l a apresentada a segu i r , mostra-se o námero de arcos que 
foram considerados como " in f in i to" (n xlO), para cada grafo pelos s is temas B- 
6700 e IBM-1130. 
T A B E L A 4 
B-6700 
2 
12 
33 
2 . 00tenção de tempos 
Em todos os programas 02 tempo medido relaciona-se apenas com 
a s -modificaçÕes da matriz de d i s t anc ias o r i g i n a i s a t é s e r obt ida . a matr iz de 
custos mínimos, não eseando envolvida nenhuma l e i t u r a ou impressão ou chama- 
das de ':£ unçães ou subrot inas , ~ambém e m nenhum dos programas apresentados é 
f e i t a obtenção dos caminhos mznimos mas tão sÕmente do custo. 
No sis tema IBM-1130 a medição é f e i t a p e l a chamada de r o t i n a s 
que trabalham com pulsos da impressora 1132. A unidade é o milisegundo e em 
tempos superiores dez segundos o ê r r o é i n f e r i o r 1%. 
No sistema B-6700, u t i l izou-se uma r o t i n a que fornece o tempo 
de processamento em unidades de 2.4 microsegundos. Es te s is tema t r aba lha com 
de memória e pa ra s e obter tempos com ê r r o i n f e r i o r 2 5% em d i f e r e n - 
t e s tomadas é necessár io a u t i l i z a ç ã o de uma opção do compilador que aloca 
toda a matriz sem segmentação. Sem a u t i l i z a ç ã o dessa opção, o tempo para 
d i f e r e n t e s tomadas é totalmente f lu tuan te , não poss ib i l i t ando nenhuma compa- 
raçao . 
Uma c~rn~lementação d i r e t a do presente t rabalho, é a já c i t a d a 
na Última seção do c a p í t u l o an te r io r . Sendo imprescindível o t rabalho com 
arquivos para grafos de grande por te , a determinação da var iação de tempo gas - 
t o pelos do i s processos com a inclusão das operações de t r ans fe rênc ia arquivo- 
memória c e n t r a l é de espec ia l i n t e r ê s s e para o usuário. 
Como os resul tados aqui obt idos , dizem r e s p e i t o ã d i f e r e n t e s 
tratamentos em têrmos de programação para procedimentos já conhecidos, um t r a - 
balho in te ressan te é a t a c a r outros procedimentos para determinação de caminhos 
&nimos, visando torná-los mais e f i c i e n t e s apenas por um mais bem estudado t r a - 
tamento computacional. É p o s s ~ v e l que procedimentos já abandonados sejam na 
rea l idade melhores que outros usualmente considerados como mais ef i c i e n t e s ,bas - 
tando u t i l i z a r naqueles alguns de ta lhes de programação p o s s ~ v e i s e m modernos 
sis temas computacionais. 
Finalmente, uma extensão n a t u r a l d e s t e estudo em que s e mostra 
s e r o procedimento d e - D i j k s t r a mais e f i c i e n t e que o procedimento de Floyd, & a 
ve r i f i cação do comportamento do procedimento A* como apresentado por H a r t , N i l s - 
son e Raphael 1 1 e por Nilsson 1 l 3 I . Nestas r e fe rênc ias prova-se que pa- 
r a o problema de determinação do menor caminho e n t r e do i s pontos, o procedimen - 
t o A$k é mais e f i c i e n t e que o procedimento de Di jks t ra ; dispondo-se então de u- 
ma informação adic ional sobre o grafo, que permita o estabeleciménto de uma 
"função de avaliação1', é aparentemente p o s s ~ v e l e s t abe lece r r eg ras pa ra a a p l i - 
cação e f i c i e n t e do procedimento A* a cada p a r do grafo(n2 aplicações) e deter - 
minar então s e para e s se problema(de determinação do menor cus to e n t r e cada par 
de v é r t i c e s de um grafo orientado com arcos de custo pos i t ivo) a e f i c i ê n c i a a in - 
da é superior do procedimnho de Di jks t ra . 
observação espec ia l - Es te trabalho es tava terminado, quando por uma re f erên- 
c i a de Grassirn e Minoux 1 ' Idescobriu-se o t rabalho de Yen 1 l 5 ] e pos te r i - 
ormente Williams e White / l 8 1 e ainda Yen 1 l 6 1 . 
A i d é i a desenvolvida por Yen e m 1 l 5 1 e 1 l6 1 é a mesma aqui 
apresentada, embora a s m o d i f i c a ç ~ e s não sejam f e i t a s sobre a ma t r i z o r i g i n a l 
de cus tos e s&m sÔbre um v e t o r a u x i l i a r , O procedimento d e Yen u t i l i z a por- 
t a n t o um v e t o r ad i c iona l (n posiçÕes a mais d e memória) e d i z o a u t o r t e r ob - 
t i d o r e s u l t a d o s próximos ao teoricamente esperado. 
36 
R E P E R Ê M C I A S 
I ' I B i l d e , Ole and Krarup, Jakob, "A Modified Cascade Algor i thm f o r shorstest 
Pahhs (C)". FETPA, v o l . V I I I , n? 2 , p.231.-241 (1969). 
1 1 Dreyfus , S t u a r t E., "A.n A p p r a i s a l o f Some Shor tes t -Pa th Algor i thms" . 
OPERATIONS RESEARCH, v o l . 17 , no 3, p.395-412 (Maio-1969). 
1 1 Edmondç , J a c k and Karp , Richard M. , " T h e o r e t i c a l Improvenients i n 
Algor i thmic E f f i c i e n c y f o r Network Flow Problems". JOURKAL OF THE 
ACM, v o l . 19 , n' 2 , p.248-264 ( a b r i l - 1972) . 
1 1 Elmaghraby , S a l a h E . , "The Theory o£ Networks and Management Sc ience" . 
P a r t I . 1-fANAGE?fENT SCIENCE, v o l . 1 7 , no 1, p.1-34 (Setembro - 1970) . 
1 1 Farbey, E.A., Land, A.1-I. and Yurchl-and, J . D . , "The Cascade Algor i thm 
Por F i n d i n g A11 S h o r t e ç t D i s t a n c e s I n a Di r e c t e d Craph". MANAGEMENT 
SCIENCE, v o l . 1 4 , no 1, p..1.9-25 (Setembro - 1967) . 
1 1 Ployd , Rober t W . , "Algorithm 97 - S h o r t e s t Path" . COMMiJPJICATIONS OP 
TBE ACY, v01 . 5 , n? 6 , p. 345 (Junho - 1962) . 
1 ' 1 G r a s s i n , J . e % Yinoux, 'r-. , " V a r i a t i o n s Sur Un Algoritlime D e D a n t z i g - 
A ~ p l i c a t i o n A La Recherche Des P lus C o u r t s Chemins Dans Les Grands 
Reseaux". R.A.I.R.O., v o l . 1, p. 53-61 (Yarço - 1973). 
1 1 Hart , Pe te r E . , Nilsson, Nils J. and Raphael, Bertram, "A Formal 
Basis For The Heuris t i c Determination o£ Minimum Cos t Paths". 
IEE TP&I'JSACTTC)FS OP S.S.C., vo l . SSC-4, n? 2 , p. 100-107 (Julho-1968). 
1 1 Johnson, Donald B . , "A Note on ~ i . j . k s t r a ' s Shor tes t Path Algorithm". 
JOURNAL OF THE ACT4, vo l . 20, n? 3, p . 385-388, (Julho - 1973). 
1 ' O 1 Johnson, E l l i s L . , "On Shor tes t Paths and Sor t ingt t . I B M - RC 3691 
( 16719) - V-THEXATICS (Janei ro - 1972). 
I 1 ' Kniith, Donald E . , "The A r t O£ Computer Programming", vo l . I , 
"Fundamental A1 gorithms ", ADDISON WESLEY P .C. (1968) 
1 l 2 1 Minieka, Edward, "On Com~uting Sets o£ Shor tes t Paths I n a Graph". 
COWNICATIONS OP THE ACY, vo l . 17, n? 6 , p . 351-353 (Junho - 1974). 
/ l 3 1 Nilsson, Nils J . , "Problern - Solving Methods I n A r t i f i c i a l In t e l l igence" . 
YcGPAW-HILL , Inc . (19 71) . 
1 l 4 1 Roy, B. , "hlpjébre Noderne e t ~ h é o r i e des Graphes" - Tome 2 - "Applications 
e t ~ r o b l è m e s Specifiq,ues". Pasc icule 2. DUNOD (1970). 
1 l 5 1 Yen, J i n Y . , "Finding The Lengths o£ A 1 1 Shor tes t Paths I n N-Node 
N~ Additions Nonnegative - Distance Complete Network Using --- 
2 
and N~ Comparisons". JOURfiJAL OP THE ACY, vol . 19, n? 3 , p. 423-424, 
(Julho - 1972). 
I 'v , "Reply t o Williams and White's ~ o t e " . JOURNAL OF THE 
ACM., vo l . 20, n? 3, p. 390 (Julho - 1973). 
( l 7 ( Whiting, P.D. and H i l l i e r , J . A . , "A Method For Finding the Shor t e s t 
Route Through A Road Network". OPERATIONAL RESEARCH QUARTERLY, v o l . 
11, n? 1 /2 , p. 37-40 (1960). 
1 l 8 1 Williams, Thomas h., and TJhite , Gregory P . , "A Note On Yen's 
Algorithm f o r Finding The Length of A 1 1 Shor t e s t Paths I n N-Node 
Nonnegative - Distance Networkst'. JOURNAL OF TI-IE ACM, vo l . 20, n? 3, 
p. 339-390, (Jul.ho - 1973) 
OBS : ~ e f e r ê n c i a s 1 1 , I I e 1 l 4 1 não são c i t adas no t ex to . 
A P E N D I C E I 
FLOYD - Procedimento de Floyd sem modif icaGÕes (IBM-1130) 
/ / F C F 
* L I S T SCLPCE P P C C R D P 
" C P E kCFC IhTECfRS 
5LCPCtTfRE PLEPtIX1IY7YFL) 
lL=IX*E1C 
IF(IY)?,t,E 
5 lY=1?+?2767+1 
t Y F L = I Y 
YFL=YFL/?27Éi 
I X = I? 
P E T L F N 
EhC 
/ / C L F 
"STCPE h S U P ALEP 
/ / FCIF 
* L l S T SCbPCE PFCGRFP 
"ChE h C F t IhTECERS 
SLEFCUTIRE P D N C 
Ib7ECEF C(9CySC) 
CCFPCh hpCqhPP4 
hPP4=C 
I X = 3 L 7 C 7 
StF=h*lC 
[C 1 I=111\: 
CC L J= l , l t 
S CPLL bLE!t 1 x 9 IYVYFL 
IF(YFL-a5)4?4,3 
4 IF(f-J)e,.?E 
e C ~ L J I = ~ U P 
bFF4=NPP4+1 
C C T C L 
3 CLLL PLEB(IX,IY,LFL) 
IF ( Y F L - * 1 1 3 ~ 37 11 
11 CI19J)=YFL*1C. 
2 CCPTIRLE 
1 C(I,I)=C.C 
FETLFP 
E\ C 
I / LUF 
*STCPE hS U P PPRC 
/ / FCF 
" L I S T 5 C L P C E FFCGPPP 
*ChE kCPC IRTECER5 
"ICCSt L 5 f l F E P C E P ~ 1 4 ~ 3 P P I N T E R ~ O I S K ) 
r FFCCFbP! FPIhCIFfL FLt??C S f P MCCIFICPCCES 
IPTECEF CISC1ÇC)rCt 
CCPPCR h? C, h b P 4 
h = 3 
1C CDLL FPNC 
CPLL S T b R T 
E C 1 K = l , [ \ i 
c c i I=lln 
EC 1 J = l , R 
CL=C(I,K)+C(KpJ) 
FLOYJI - Procedimento de Ployd sem m6dificaGÕes (B-6700) 
CCMP I 
C SUBR 
* S E T L 
L E FLOYD FURTRAN 
. C T I N A PARA GERAR 
n b T t\ 
ELEMEkJTnS DA V A T R I Z DE D I S T A N C I A S 
9 XAt~ l t t 
C h C 
S U e R C U T I N E RAND 
C O P P C N N , Q ( 99999 
EkC 
E S T E PROGRAMA T f P ? C1 LONG 
ET LCNG 
P R O G R A P A P R I N C I P A L F L O Y D SEK 
R E A L MENOR 
LOPPCN N 01 9 Ç T 99 1 , NAV4 
h=? 
l g C P ~ L R A N D 
T E P P C = T I M E ( 1 2 ) 
CC 1 K = l r N 
UMERO D E ARCOS I G U A I S A 
' r / I 
I N F I N I T O 
80 h=IV+3 
GO T C 10 
90 STCP 
EN C 
EPiC JCE!. 
P.E.L.C.C. - Procedimento de Floyd ev i tando l i nhas e colunas p o r 
comparações (IFIB-1130) 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 
D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 
E
L
E
T
R
O
N
IC
A
 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 
D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
~
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 E
L
E
T
R
O
N
IC
A
 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 D
O
 
R
IO
 D
E
 J
A
N
E
IR
O
 
N
Ù
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 E
L
E
T
R
O
N
IC
A
 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 
D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 
E
L
E
T
R
~
N
IC
A
 
X
 
CJ 
rn
 
-I
 
r
-
 
C
I 
C
L
 
rn
 
O
 
r>
 
O
 
c
r
h
J
P
\
>
1
\
 
1
0
 
C
. 
15
3 
.B. 
m
n
m
m
7
-
 
II
 
n
~
4
n
n
t
-
i
m
n
~
m
u
m
 
7
h
h
n
 1
1 
-r
i 
-
~
n
r
n
h
P
,
n
~
-
n
?
n
n
 
C
)
F
r
 
7
-
r
 
7
J
w
T
Y
7
7
7
M
-
I
I
 
- 
r
r
-
t
.
l
-
7
c
7
-
i
T
7
r
4
4
4
r
 
n
m
L
-
 
n
w
 l 
b
h
m
n
 
U
U
W
C
-
-
 
t 
h
*
 
m
 r
i
 
\
n
u
 
4
-
 
i1 
4
7
7
7
-
M
U
X
 
X
b
r
 
r
i
\
-
\
n
-
w
C
C
c
 
I
I
u
 
* 
-
L
 
M
Ã
~
C
~
 
u
-
 
-
r
 
x
~
r
n
n
r
n
~
~
~
r
 
II
 
4
 m
 
m
-
 
4
\
m
 
C
-
U
~
J
U
 
O
 
;
?
*
?
r
-
 
I 
&
*
 
V
 
r
 
4
r
-
O
X
 
t
/
1
7
r
l
 
\
n
r
n
?
7
0
-
 
r
 ~
.
r
 
nr
 
~
i
7
m
r
 
r
,
 
u
X
*
 
.#
 
T
X
Z
r
 
C
-
'-
 
c.
i 
4
 
.?
I .
7
 b
. 
u
 
h
>
 C
 I
J
 
O
 
11
 
7
 
r
-
 
r
m
 h
 
C
,
 
- 
m
*
 
n,
 
n
 
-
i 
.O 
r
 2
 r
r7
 
w
 
s-3
 
c7 
2
 
A
 
b
 
<
n
 T
I 
(
L
)
 
n
 
* 
II
 
- ..
 
.#
 
tn
 
w
 
rn
 h
>
 
m
 r
 
C
 \
 
2
'-
 
D
 
- 
n
 
tn
 
7
 
-
r
 
.. 7
 
rn
 
- .o
 
8
7
 
w
 
m
 
F.E.L.C.C. - Procedimento de Floyd evitando linhas e colunas por 
comparações (B-6 700) 
U
N
I
V
~
K
~
I
U
A
U
~
 
I
-
t
U
t
K
A
L
 
U
U
 K
IO
 
D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
Á
O
 E
L
E
T
R
O
N
IC
A
 
O
O
*
O
 
&
r
)
 
V
, 
V
, 
O
 
rn
 
~
u
r
n
y
'
 
r
n
m
a
 
7
a
m
 
4
 
+
-
r
 I
-
 
r
 
I
- 
n
w
+
w
 
+
c
?
=
 
r
; 
O
 
a
 
O
 
W
N
N
S
Z
 
'W
 
r
 
3
 
x
n
 
-I
 
v
fu
a
 
co
 
L-
LU
 
O
c
o
 
8
 
n
m
r
m
 
r
-
X
W
 
C
m
~
~
7
w
l
l
n
~
-
i
0
0
~
0
~
n
u
m
~
r
)
n
i
~
]
/
2
o
m
b
;
0
t
i
 
r
n
m
~
~
n
w
X
A
7
m
~
~
x
n
m
W
~
7
0
~
,
n
~
~
 
o
z
-I
n
 1
1 
t
l
 
-
O
w
r
n
o
c
c
-
-
n
t
n
o
n
n
n
m
~
b
 11 
C
m
l
o
P
7
v
Z
n
i
-
n
-
n
-
I
~
D
-
n
n
4
O
n
C
Z
~
O
C
~
i
m
 
m
r
ln
 
Z
-
u
 
W
1
4
7
Z
a
Z
u
-
 l
l 
c.
. 
7
f
'-
l
~
'2
'b
b
.
~
~
X
r
i
-
i
w
Z
u
-
I
I
 ?
I
-
-
-
 
ll
 
T
! 
I1
 ?
r
-j
r
C
O
W
 
7
3
-1
 +
 67
c
iX
-I
-n
-i
-i
4
*
 
T
i
n
L
w
~
N
w
-
c
r
 T
f
 0
3
2
 
C
3 
C
* 
-
I*
 X
;J
d
&
- 
u
X
;O
l\
.)
w
 li
 l
V
&
P
c
T
X
 
Z
n
 
T
]l
d
 
I 
&
D
m
C
Ic
ic
c
L
--
 
I
 N
 I 
O
 
O
 
O
 
Ci
) 
Ã
3
u
w
L
-
lD
r
i 
II 
C
 I
 4
P
 
7
-
5
 11
 0
0
 
?>I- 
4
-
 
4
-
 ll
 Z
Z
Z
-
u
u
F
 
it
7
;k
X
 11
 F
 
2
X
r
;'
iU
 
k
 
Z
-
Z
-
 
l 
Z
 
2
-
C
 
I 
Z
L
H
%
,
+
+
O
Z
C
 
O
 
C
. 
~
\c
.o
\c
.C
C
C
 1
1 
- -L
-
 
II
 
11 
-
i
>
 m
m
C
n 
n
, 
li
 C
 1
1 
I
-
n
N
b
 11
 -
0
 
n
 11 
i1 
r
a
 
-4 
-
1
4
 
U
 
-
4
 
0
-
 
-
im
m
r
n
c
~
tK
r
 
ll
 r
r
r
~
Z
 
Z
Z
 
w
 
X
 
o
~
X
*
 
C-
i 
3
m
~
u
i
G
ç
l
'
r
d
C
j
~
 
Z
W
 
b
0
 
m
 - 
-J
w
 
r
.,
, 
c
~
.-
W
i'
r-
 
- 30
 
1
 
3
 
Z
 
E
-
 
4
.
3
.
7
 &
C
*
 -
3
-
 *
 
.rZ
 
;o
 
i-. 
Z
O
X
 
I 
+*
 u
 
Z
2
:
v
 
r3
73
 
O
 
C
3 
--
 +
v
~
>
w
-z
L
' 
o
rn
 
3
r
-7
 
-i
~
-r
n
 
0
;7
r
Z
r
u
 
- 
- 
w
 
4
 
m
ri
 
v
 
*
-
H
 
C
, 
a
r
n
~
r
-
 
C
-N
 
- 
r
 
\D
 
u
m
 
* 
Z
 
&
w
Z
 
9
P
 
0
%
 
B
II
cr
n
.r
 w
 
-
X
*
 
r
 
N
 
\O
 
P
 
Lz
 
C
,
 
.. 
a
b
.
 
6
1
-
1
 
* 
-O
?
J
r(
V
 
v
-
L
J
W
 
Y
 
4
 
r
 
* 
.'&
 
CC
 
Z
 
m
x
'
 
a
o
a
P
-
 
P
J
C
ir
, 
\O
 
3
 
a
w
 
\
U
f
l
 
T
1
b
 
O
11
 
x
1
 
.. <
v
 
4
 
f
i 
0
 
w
 
a
 
F
LP
 
-
D
a
4
 
v
 
w
 
* 
rn
- 
rn
 
r,) 
.a 
& 
e
 
rr
! O
 
n
 
4
X
 
.. 
z
 
.<
 
;7
 
z
 
r
&
 
w
z.
n
7
C
7
 
P
' 
ç
. 
=
o
 
13
, 
!
T
4
 
-
3
3
2
0
 
iZ
 
I
 
-
2
 
I
D
.
 
* 
(
n
u
-
 
c.
 
r!
i 
i'
 
ri
1
 
CP
 
r
n
 
',
 
4
 
.k
 
<
 
L[
. 
-4
 
II
 
5
)
 
I"
 
-i
 
-
i
 . 
-
i 
n
 
L
J
 
- 
-C
 
D
 
V
i 
.b
 
ui 
V
7
4
 
\
 
:z
 
m
~
.3
 r
 
3
 
U
 
3
-
 
r'?
 
(7
 
G' 
c\ 
:. 
Z
u
 
3.
 
r
 
T
 
0
-
 
u' 
W
 
p.
 
C
) 
":
 
4
 
C
A
Z 
I
 
F
 
-
C
 
3
 
u
 
- x
 
V
i 
P
u 
'.m -
7
3
 
v
i 
t?
 
O
 
rn
 
O
 
r
; 
o
 
a
 
m
 
i- 
W
 
C
 
V
> 
D
 
Z
 
-
i 
X?
 
P
 
3' 
n
 
V
)
 
z
 
,r
l 
n
 
V
> 
10
 
u
 
c
-
(
 
C
 
P
 
73
 
V
> 
I;
, 
C
 
P
 
W
 
V
1 
P.E.L.C.D. - Procedimento de Floyd evi tando l i n h a s , colunas e diago - 
na1 (IBM-1130) 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 D
E
 C
O
M
P
U
T
A
Ç
A
O
 
E
L
E
T
R
d
N
IC
A
 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 E
L
E
T
R
~
N
IC
A
 
F.E.L.C.D. - Procedimento de Ployd evitando l inhas , colunas e diago - 
na1 (B-6700) 
C C P P I L E FLGYD FOKTKPN 13ATA 
C SUf?KCTINA P A R A G E R A R fLkFl';.ilT@S DA F'ATRIZ DE D I S T A N C I A S 
P S E T 1 CNG 
S U P = N 
C0 1 
CC 2 
XT=RA 
I F ( X T 
3 I F ( I - 
4 LIIVJ 
N A V 4 = 
G C TC; 
8 XT=RB 
I F ( X T 
9 C(I,J 
2 C U N T I 
3. C ( I , 1 
RETUR 
f k C 
E S T E PROG 
PROGRAPA 
ET L O N G 
R EbL 
COPPC; 
R P M 6 
P R I N C .CVIT I \NDO LINHAS, COLUNAS E D I 
4 
AGONAL 
1\=3 
13 C 4 L L RANC 
2)-7fMPU)"~2.4/lf~*~6 
t \ lAP4 9 TEMPC1 
KCI CE NOS = ' , I 2 , / , ' N 
PU=', F10.69 ' SEGUNDOS 
r 90 
DE ARCOS I G U A I S A f N F I N P T O 
h=b!+3 
G O T C 10 . 
S T C P 
E N E 
JUB e END 
F.E.L.C.V. - Procedimento de FLOYD evi tando l i n h a s e colunas por v e t o r 
(IBM-1130) 
.
-
.
-
 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 
D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 E
L
E
T
R
~
N
IC
A
 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 
D
O
 R
IO
 
D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 
E
L
E
T
R
6
N
lC
A
 
7
 
6
 
n
 
i
t
.
~
 
$
A
 
%
 
&
.
c
,
 Z
C
\ 
.+ 
O
 '
*
, 
u
~
l
r
\
m
z
c
 
n
r
-
\
t
n
\
 
f
-
lr
-
x
 
-
n
n
7
w
 
-i
 
7
 u
 
-
-
I 
7
 
u
 
I-J 
w
 
x
in
r
n
m
-
n
n
r
?
 
C
L
 
m
<
n
n
n
n
 
m
m
-
n
 
r
 
O
 
n
t
n
 
4
n
m
r
 
P
R
)
~
 
(
(
J
 
M
J
-
. 
\O
 
-
I
D
X
C
 
m
 t
n 
-
i
 n
 
a
-
r
 
m
m
-
n
 
s
 
z
m
u
 
s-
 
x
i 
m
~
n
n
~
7
n
m
w
r
n
f
u
n
~
 
m
m
m
n
m
r
n
A
7
m
u
~
n
n
n
m
w
7
n
m
m
n
~
n
 
r
n
n
u
~
~
~
~
~
~
m
~
n
 
n
7
n
-
h
 I
I 
n
~
i
7
b
~
n
m
n
 
7
m
-
m
-
~
b
n
a
-
n
n
b
n
n
C
x
b
~
,
7
C
m
m
 
7
r
n
x
-
1
-
1
n
-
C
n
4
C
m
n
 
r
i 
I
-
I
-
I
~
~
?
T
~
?
C
J
~
~
 
n
4
~
7
~
+
-
.
~
 
7
u
*
-
r
 
-n
 
li
 
?
?
-i
-n
t-
iC
E
 
m
-
4
 
11
 
i-
r
 
I1 
- I
1 
m
n
C
 
r
-
r
r
r
 
T
r
n
r
n
b
w
 
a
 
C
-
 
4
-
 
-
<
r
d
~
u
 
r
d
-
C
T
N
r
 11
 
t
d
h
?
m
f
l
 
7;
i 
r
u
 II 
II 
u
w
w
x
 
x
 
u
 w
 
m
7
f
i
 
m
u
n
 
T
l
r
u
C
n
 
í
7
l
i
~
 
l
n
 
7
1
\
i
 
11
 
n
n
n
d
n
 
?
i
d
-
e
~
-
e
-
c
x
n
~
r
>
 
X
-
 
(
n
z
 
7
~
m
u
~
r
7
r
n
 
7
-
7
-
r
b
 
7
e
~
r
b
.
~
~
a
-
,
~
r
>
7
m
C
7
r
n
 
Z
 
-
n
<
+
-
&
.
C
7
m
 
Il 
II
 
Y
 
4
 
h
 
u
n
x
e
.
4
 
r
 
11
 
r- 
i1 
I 
I
-
~
b
 
11
 
- I
 
r
 1
1 
i1 
-r
n
 
70
 
4
 -
i 
5
- 
r
 
i
g
i
n
a
-
i
-
4
 
~
u
i
l
b
7
 
z
n
 
u
~
7
m
-
n
 tn
 
~
"
ir
r
-
r
:
*
 m
 
7
t
~
f
!
5
*
 r
n
r
r
e
s
4
1
 
7
 
~
m
u
 
(n
 
zc
 
\O
-
m
 
a
 
* 
*
=
r
i
 
* 
7
[
1
7
M
O
X
)
 
n
 
&
?
.
r
 
t
n
b
*
 
.r
 
- m
7
c
f)
n
í 
LJ
J 
4
m
a
7
n
w
 
7
 
*
-
I
 
r?
 
-
o
;
c
i
r
r
i
n
 
O
 
r-
--
 
+
Ü
~
-
-
P
Z
 
r
i
-
r
n
m
n
 
n,
 
m
*
 
r
r
ir
ii
a
 
7
 
V
 
ç
-
i
\
D
u
-
 
7
5
~
3
 
C
 
3
i-
1
3
n
 
C
 
u
 
I
c
w
 
* 
.i3 
7
0
0
 
C
 
4
 
4
C
-
P
 
W
 0
 
7
7
t
7
U
r
V
)
h
)
 
h
 
c
-i
- 
X
 
a
*
 x
 
z
I
"
>
W
W
X
 
'E
. 
CI
\ 
+
 
b
 W
7
3
 
b
r
?
r
 
-
h
 
b
 
c
!
 (
L
)
 u
 
A
 v
 
b
-
 
b
 
b
 
I
 
u
 
r
 
h
 
?
-
a
r
-
 
7
 
a
 
i.
 
u
 
- -
 
t
.
n
z
 
7
 
rn
 
7
 
h
a
r
a
 
td
 
;t
 
W
 
4
 
1
0
 
-C
 
h
 
r
i
 
C7
 
b
 
b
 
o
-
n
u
 
'D
 
w
 .. 
.. 
- 
r
 
- 
-.. 
r
h
)
 
7
 
4
 
-C
 
rn
 
Y
 
r
i
n
~
 
r-
~ 
-n
 
n
 
'D
 
x
 
C
4
7
 
r
 
i- 
.. 
;7
 
4
 
V
 
- 
ií?
 
4
 
ri
1
 
W
 
-.
 -C
 
H
 
c
 
- 
4
 4
 
r
 
3
 ;
n
 
- 
.c
 x
 
0
 -
 
O
 
r
 
W
 
7
 
I
 
P
 
tn
 
rn
 
O
 
n
 
r
 
r
 
2
 
5
 
V
, 
u
 
n
 
75
 
<
 
rn
 
-I
 
r
)
 
X
I 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
VC
LE
O
 
D
E
 C
O
M
P
U
T
A
Ç
Á
O
 E
L
E
T
R
~
N
IC
A
 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 D
O
 R
IO
 
D
E
 J
A
N
E
IR
O
 
N
VC
LE
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 E
L
E
T
R
~
N
IC
A
 
F.E.L.C.V. - Procedimento de PLOYD &ií%tando l inhas e colunas por vetor 
(B-6 700) 
A P E N D I C E 11 
DIJKSTRA - P~ocedimento de Dijkstra com modifícaçÕes (IBM-1130) 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 D
O
 R
IO
 
D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 D
E
 C
O
M
P
U
T
A
Ç
A
O
 
E
L
E
T
R
~
N
IC
A
 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 
D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
A
O
 E
L
E
T
R
6
N
IC
A
 
1L
 
.&
 
A
r
-
\
 
7
 
u
 
m
m
n
 
C
P
 \
n
 
-I
 
n
 
U
N
IV
E
R
S
ID
A
D
E
 
F
E
D
E
R
A
L
 D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
O
C
LE
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 
E
L
E
T
R
~
N
IC
A
 
U
N
IV
E
R
S
ID
A
D
E
 
F
E
D
E
R
A
L
 D
O
 R
IO
 D
E
 J
A
N
E
IR
O
 
N
Ú
C
L
E
O
 D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 E
L
E
T
R
~
N
IC
A
 
X
 
\D
 
rn
 
-1
 
rn
 
O
 
0
 
r
,
 
w
d
l 
4
L
n
m
 
<
r
)
 
&
 
rn
 m
n
n
m
7
u
~
~
~
b
~
n
~
n
~
~
i
n
~
n
~
~
~
~
~
u
~
n
7
n
W
~
~
-
r
)
~
~
~
~
 
7
h
h
~
I
~
n
r
C
\
'
I
-
l
m
~
~
~
~
x
m
~
h
f
i
w
n
m
m
~
7
L
n
r
i
n
r
i
m
n
t
n
r
,
T
X
r
n
L
7
 
n
l
-
r
 
7
'
7
-
 
m
w
-
i
p
l
-
7
7
 
11
 
7
A
Y
-
 
I1
 
I1 
7
 
I1
 
II
 
t
l 
I1
 
I1
 
7
 
I1
 
7
-
 
I!
 
II
 
7
 
II
 
m
 
I
-
I
-
-
~
+
~
U
-
P
-
-
I
T
I
~
-
-
I
-
-
I
X
~
R
Y
 
m
n
~
\
n
n
,
,
c
-
~
~
7
-
r
c
n
n
~
i
~
~
>
n
~
-
 
r
~
(
~
~
l
h
b
r
n
r
i
 
u
u
 
m
-
u
-
-
7
 
z
7
n
u
7
 
l
w
 
-
m
-
7
 
m
7
w
 
r
n
 
T
 
a
-
 -
4
.-
-I
l 
4
7
Z
 
I1 
M
Y
W
Y
~
X
 
I
I
~
+
?
;
C
J
C
W
~
 11
 
U
~
C
 
II
T
J
-
 
X
b
i
-
~
 r
)
\
-
\
n
-
u
C
T
 
r
l
v
 
-
r
 
.
i 
c
 
II
 
m
-
r
-
-
n
 
C
 
m
w
 
6
 
I1 
n
-
 
11
 
1
-
1
7
3
0
 
--
 a-.
 
X
X
W
m
 
-
U
I
I
 
M
L
X
U
-
H
 
II
 
u
 
II
 
rn
 
--
w
C
W
*
 
C
-
N
W
 
4
 
m
 
- 
-.
~
\m
 
U
H
~
M
L
+
X
~
X
 
U
X
N
 
W
C
-
Y
 
W
-
 
(3
 
7
n
r
-
 
U
-7
 
u
 
c
 
I 
u
 
C
 
7
 
t
 
- rn
 
Y
 
7
 
n
 
30
 - i3 4 13 .. ir) 
DIJKSTRA - Procedimento de Dijks tra com modif icacÕes (B-6700) 
LCNG 
G C C CIJMSTRA M O C I F 1 C A i i O 
R E A L MENOR 
U
N
IV
E
R
S
ID
A
D
E
 F
E
D
E
R
A
L
 
D
O
 R
1
0
 D
E
 J
A
N
E
IR
O
 
N
~
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 
E
L
E
T
R
~
N
IC
A
 
. 
U
N
IV
tK
Ù
.I
U
A
U
k
 
k
k
U
k
K
A
L
 U
U
 K
I
U
 U
k
 J
A
N
C
IK
U
 
N
Ú
C
L
E
O
 
D
E
 C
O
M
P
U
T
A
Ç
Ã
O
 
E
L
E
T
R
~
N
IC
A