Algoritmo Bellman-Ford Java

algoritmo bellmand-ford java

Algoritmo de Bellman-Ford en java para buscar el camino mínimo desde un vértice al resto de vértices en un digrafo (con posibles pesos negativos en las aristas). Detecta si hay ciclos negativos y nos devuelve los vértices predecesores. El grafo hay que introducirlo por consola según las instrucciones que se muestran en la ejecución.

El algoritmo de Bellman-Ford genera el camino más corto en un grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos, salvo que el grafo sea dirigido y sin ciclos. Por lo que el Algoritmo Bellman-Ford en java normalmente se utiliza cuando hay aristas con peso negativo.

Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.

Según Robert Sedgewick, “Los pesos negativos no son simplemente una curiosidad matemática, surgen de una forma natural en la reducción a problemas de caminos más cortos”, y son un ejemplo de una reducción del problema del camino hamiltoniano que es NP-completo hasta el problema de caminos más cortos con pesos generales. Si un grafo contiene un ciclo de coste total negativo entonces este grafo no tiene solución. El algoritmo es capaz de detectar este caso.

Si el grafo contiene un ciclo de coste negativo, el algoritmo lo detectará, pero no encontrará el camino más corto que no repite ningún vértice. La complejidad de este problema es al menos la del problema del camino más largo de complejidad NP-Completo.

Más información sobre el algoritmo de Bellman-Ford en wikipedia.

Consulta otros algoritmos que tenemos publicados desde este enlace.

/*
 * Miguel Angel Sánchez Fernández
 * masfernandez.com
 * Algoritmo Bellman-Ford Java
 */
package algoritmicaAvanzada;

import java.io.*;
import java.util.*;

public class BellmanFord {

    private LinkedList aristas;
    private float etiquetas[];
    private int predecesor[];
    private int numeroVertices, totalAristas, nodoOrigen;
    private final int INFINITY = 999;

    private static class Aristas {

        int origen, destino;
        float coste;

        public Aristas(int a, int b, float c) {
            origen = a;
            destino = b;
            coste = c;
        }

        @Override
        public String toString() {
            return "Aristas{" + "origen=" + origen + ", destino=" + destino + ", coste=" + coste + '}';
        }
    }

    public BellmanFord() throws IOException {
        float item;
        aristas = new LinkedList();
        DataInputStream in = new DataInputStream(System.in);
        System.out.print("Introduce numero de vertices ");
        numeroVertices = Integer.parseInt(in.readLine());
        System.out.println("Matriz de costes");
        for (int i = 0; i < numeroVertices; i++) {
            for (int j = 0; j < numeroVertices; j++) {
                if (i != j) {
                    System.out.println("Introduce coste del nodo " + (i + 1) + " al nodo " + (j + 1));
                    item = Float.parseFloat(in.readLine());
                    if (item != 0) {
                        aristas.add(new Aristas(i, j, item));
                    }
                }
            }
        }
        totalAristas = aristas.size();
        etiquetas = new float[numeroVertices];
        predecesor = new int[numeroVertices];
        System.out.print("Introduce el vertice origen");
        nodoOrigen = Integer.parseInt(in.readLine()) - 1;
    }

    private void relajoArista() {
        int i, j;
        for (i = 0; i < numeroVertices; ++i) {
            etiquetas[i] = INFINITY;
        }
        etiquetas[nodoOrigen] = 0;
        for (i = 0; i < numeroVertices - 1; ++i) {
            for (j = 0; j < totalAristas; ++j) {
                System.out.println(aristas.get(j));
                if (etiquetas[aristas.get(j).origen] + aristas.get(j).coste < etiquetas[aristas.get(j).destino]) {
                    etiquetas[aristas.get(j).destino] = etiquetas[aristas.get(j).origen] + aristas.get(j).coste;
                    predecesor[aristas.get(j).destino] = aristas.get(j).origen;
                }
            }
            for (int p = 0; etiquetas.length < p; p++) {
                System.out.println("\t" + etiquetas[p]);
            }
        }
    }

    private boolean ciclo() {
        int j;
        for (j = 0; j < totalAristas; ++j) {
            if (etiquetas[aristas.get(j).origen] + aristas.get(j).coste < etiquetas[aristas.get(j).destino]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String args[]) throws IOException {
        BellmanFord bellman = new BellmanFord();
        bellman.relajoArista();
        if (bellman.ciclo()) {
            for (int i = 0; i < bellman.numeroVertices; i++) {
                System.out.println("Coste desde " + bellman.nodoOrigen + " a " + (i + 1) + " =>" + bellman.etiquetas[i]);
            }
            for (int i = 0; i < bellman.numeroVertices; i++) {
                System.out.println("El predecesor de " + (i + 1) + " es " + (bellman.predecesor[i] + 1));
            }
        } else {
            System.out.println("Hay un ciclo negativo");
        }
    }
}

Valora el artículo aquí si te gustó:

Comments

  1. Anonimo says:

    Amigo que dato se introduce cuando te pide el vertice origen? Muy buen aporte, muchas gracias.

  2. christo816 says:

    como se compila tu algoritmo?

    1. Jeced Alejandro says:

      Crea un nuevo proyecto en java y asignas el nombre BellmanFord

      1. Anónimo says:

        Dos años después..esperemos que le sirva;)

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *