Grafos: Caminho Mais Curto 

Caminho Mais Curto:  Uma Implementação simples na linguagem C, usando o módulo de listas de adjacência.
 
Exercício:  Implemente um módulo de grafos pesados usando listas de adjacência.

Um dos problemas típicos em grafos pesados consiste em determinar  o caminho mais curto entre dois vértices. O algoritmo apresenta-se de seguida.
 

função CaminhoMaisCurto (GRAFO g ; VERTICE u,v)  : (PESO , VERTICES )
vis = {}
(hacaminho,peso,caminho) = CaminhoMaisCurtoAux (g,u,v,vis)
se         hacaminho então CaminhoMaisCurto = (peso , caminho U {u})        /* partimos de u */ 
senão  CaminhoMaisCurto  = (0,{})
 
 
função CaminhomaisCurtoAux (GRAFO g ; VERTICE u,v ;  VERTICES vis) 
                                                                : (Bool , PESO , VERTICES)
vis = vis U {u} ;
se        u = v então                    /* chegamos a v */
             b = verdade
             peso = 0
            caminho = {}
senão  b = falso;
             peso = MAX
             caminho = {}                                              /* vertices intermedios */
             para w in (sucessores(g,u) - vis) fazer
                     (b',peso',caminho') = CaminhoMaisCurtoAux(g,w,v,vis);
                      se b' então
                            b = b ou b'
 peso' = peso' + peso(g,u,w)
                            se peso' < peso então
                                 peso = peso'
                                 caminho = caminho' U {w}
 CaminhoMaisCurtoAux = (b, peso,caminho)

Enviar comentários para jas@di.uminho.pt.
Ultima modificação: 5/11/1998