Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Algoritmia » Camino minimo con pesos negativos en grafo

Algoritmia - Camino minimo con pesos negativos en grafo

Volver
Nuevo Tema
<<>>
 
Vista:

Camino minimo con pesos negativos en grafo

Publicado por Luis (3 intervenciones) el 28/04/2004 01:17:53
Necesito un algoritmo como el de dijkstra pero que admita pesos negativos he oido... Bellman Ford pero no encuentro seudocodigo ni explicación del coste
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Alejandro

Bellman-Ford con pesos negativos

Publicado por Alejandro (307 intervenciones) el 01/03/2024 19:34:32
Luis, el algoritmo de Bellman-Ford es una opción adecuada cuando se tratan con grafos que pueden contener aristas con pesos negativos. A continuación, te proporciono un seudocódigo básico del algoritmo de Bellman-Ford:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Algoritmo BellmanFordConPesosNegativos
 
    Función BellmanFord(grafo, nodoInicial)
        // Inicializar distancias
        Para cada nodo en grafo
            distancia[nodo] = INFINITO
        Fin Para
        distancia[nodoInicial] = 0
 
        // Relajación de aristas repetida V-1 veces
        Para i = 1 Hasta V - 1 // V es el número de nodos en el grafo
            Para cada arista (u, v, peso) en grafo
                Si distancia[u] + peso < distancia[v] entonces
                    distancia[v] = distancia[u] + peso
                Fin Si
            Fin Para
        Fin Para
 
        // Verificar ciclos de peso negativo
        Para cada arista (u, v, peso) en grafo
            Si distancia[u] + peso < distancia[v] entonces
                Escribir "El grafo contiene un ciclo de peso negativo"
                Retornar
            Fin Si
        Fin Para
 
        Retornar distancia
    Fin Función
 
Fin Algoritmo

Este seudocódigo muestra el proceso básico del algoritmo de Bellman-Ford. El algoritmo se repite (V-1) veces para asegurarse de que las distancias se han calculado correctamente, y luego se verifica si hay ciclos de peso negativo. Ten en cuenta que si hay un ciclo de peso negativo, el algoritmo no proporcionará soluciones correctas.

El costo del algoritmo de Bellman-Ford es O(V * E), donde V es el número de nodos y E es el número de aristas. La inclusión de aristas con pesos negativos implica que necesitas realizar más iteraciones que en el caso de Dijkstra, y esto aumenta la complejidad del algoritmo. Sin embargo, sigue siendo una opción viable cuando se tratan grafos con pesos negativos.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar