Complejidad algoritmo

carnd35 · #1 (**permalink**) 22/05/2011, 11:08

Hola
Alguien podria decirme que complejidad tiene encontrar la ruta mas corta en un MULTIgrafo?
He estado pensandolo mucho y no lo logro, les agradeceria mucho.

alexg88 · #2 (**permalink**) 22/05/2011, 11:14

Depende de que algoritmo utilices para encontrar la ruta más corta.

carnd35 · #3 (**permalink**) 22/05/2011, 13:06

No estoy seguro si sea Dijkstra
Estoy utilizando un algoritmo asi:

Código:

En Vertice.class:
void buscarMejorRuta(Vertice vDestino, int costo)
{
     if (soy el vertice destino)
           {
                  if (costo<menorCosto)
                           menorCosto = costo
                           retornar costo.
           }
     else
         {
            <Ciclo: para cada arco (no marcado)>
                       costoHastaAca = costo
                       costo += arco.darCosto
                       respuesta = buscarMejorRuta(vDestino, costo)
                       costo = costoHastaAca
            <Fin ciclo> 
         }
    
     retornar respuesta
}

Que complejidad tiene teniendo en cuenta que es un MULTIgrafo?

Gracias!

_Ruben_ · #4 (**permalink**) 23/05/2011, 01:49

El de Dijkstra creo que es el más rápido, y si no lo es, es bastante bueno por lo que puede usarse perfectamente.

Que se trate de un multigrafo da igual ya que puedes transformarlo para que no sea multigrafo.