/*
 * (C) Copyright 2006-2017, by France Telecom and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * This program and the accompanying materials are dual-licensed under
 * either
 *
 * (a) the terms of the GNU Lesser General Public License version 2.1
 * as published by the Free Software Foundation, or (at your option) any
 * later version.
 *
 * or (per the licensee's choosing)
 *
 * (b) the terms of the Eclipse Public License v1.0 as published by
 * the Eclipse Foundation.
 */
package org.jgrapht.alg.shortestpath;

import org.jgrapht.*;
import org.jgrapht.graph.*;

/**
 * The Bellman-Ford
 * algorithm. Computes shortest paths form a single source vertex to all the other vertices in a
 * weighted graph. Supports graphs with negative weights. Additionally the user can constrain the
 * paths by a maximum number of edges.
 * 
 * The algorithm has worst-case complexity O(nm) when n is the number of vertices and m the number
 * of edges of the input graph.
 * 
 * 
 * @param  the graph vertex type
 * @param  the graph edge type
 */
public class BellmanFordShortestPath
    extends BaseShortestPathAlgorithm
{
    private static final double DEFAULT_EPSILON = 0.000000001;

    /**
     * Start vertex.
     */
    protected V startVertex;

    /**
     * Maximum number of edges of the calculated paths.
     */
    protected int nMaxHops;

    /**
     * Tolerance when comparing floating point values.
     */
    protected double epsilon;

    /**
     * Construct a new instance of the Bellman-Ford algorithm.
     *
     * @param graph the input graph
     */
    public BellmanFordShortestPath(Graph graph)
    {
        this(graph, graph.vertexSet().size() - 1);
    }

    /**
     * Construct a new instance of the Bellman-Ford algorithm.
     *
     * @param graph the input graph
     * @param nMaxHops maximum number of edges of the calculated paths
     */
    public BellmanFordShortestPath(Graph graph, int nMaxHops)
    {
        this(graph, nMaxHops, DEFAULT_EPSILON);
    }

    /**
     * Construct a new instance of the Bellman-Ford algorithm.
     *
     * @param graph the input graph
     * @param nMaxHops maximum number of edges of the calculated paths.
     * @param epsilon tolerance factor when comparing floating point values
     */
    public BellmanFordShortestPath(Graph graph, int nMaxHops, double epsilon)
    {
        super(graph);
        this.nMaxHops = nMaxHops;
        this.epsilon = epsilon;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public GraphPath getPath(V source, V sink)
    {
        if (!graph.containsVertex(sink)) {
            throw new IllegalArgumentException("Graph must contain the sink vertex!");
        }
        return getPaths(source).getPath(sink);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public SingleSourcePaths getPaths(V source)
    {
        if (!graph.containsVertex(source)) {
            throw new IllegalArgumentException("Graph must contain the source vertex!");
        }

        BellmanFordIterator iter = new BellmanFordIterator<>(graph, source, epsilon);

        // at the i-th pass the shortest paths with less (or equal) than i edges
        // are calculated.
        for (int passNumber = 1; (passNumber <= nMaxHops) && iter.hasNext(); passNumber++) {
            iter.next();
        }

        return new PathElementSingleSourcePaths(iter);
    }

    /**
     * Find a path between two vertices. For a more advanced search (e.g. limited by radius), use
     * the constructor instead.
     * 
     * @param graph the graph to be searched
     * @param source the vertex at which the path should start
     * @param sink the vertex at which the path should end
     * 
     * @param  the graph vertex type
     * @param  the graph edge type
     *
     * @return a shortest path, or null if no path exists
     */
    public static  GraphPath findPathBetween(Graph graph, V source, V sink)
    {
        return new BellmanFordShortestPath<>(graph).getPath(source, sink);
    }

    // interface wrapper
    private class PathElementSingleSourcePaths
        implements SingleSourcePaths
    {
        private BellmanFordIterator it;

        PathElementSingleSourcePaths(BellmanFordIterator it)
        {
            this.it = it;
        }

        @Override
        public Graph getGraph()
        {
            return it.graph;
        }

        @Override
        public V getSourceVertex()
        {
            return it.startVertex;
        }

        @Override
        public double getWeight(V targetVertex)
        {
            if (targetVertex.equals(it.startVertex)) {
                return 0d;
            }

            BellmanFordPathElement pathElement = it.getPathElement(targetVertex);

            if (pathElement == null) {
                return Double.POSITIVE_INFINITY;
            } else {
                return pathElement.getCost();
            }
        }

        @Override
        public GraphPath getPath(V targetVertex)
        {
            if (targetVertex.equals(it.startVertex)) {
                return createEmptyPath(it.startVertex, targetVertex);
            }

            BellmanFordPathElement pathElement = it.getPathElement(targetVertex);

            if (pathElement == null) {
                return createEmptyPath(it.startVertex, targetVertex);
            } else {
                return new GraphWalk<>(
                    graph, it.startVertex, targetVertex, null, pathElement.createEdgeListPath(),
                    pathElement.getCost());
            }
        }

    }

}

// End BellmanFordShortestPath.java

 

Ads help maintain this website.