org.graphstream.algorithm

## Class BellmanFord

• java.lang.Object
• org.graphstream.algorithm.BellmanFord
• All Implemented Interfaces:
Algorithm

```public class BellmanFord
extends java.lang.Object
implements Algorithm```
Implementation of the Bellman-Ford algorithm that computes single-source shortest paths in a weighted digraph

The Bellman-Ford algorithm computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). Dijkstra's algorithm accomplishes the same problem with a lower running time, but requires edge weights to be non-negative. Thus, Bellman-Ford is usually used only when there are negative edge weights (from the Wikipedia).

## Example

``` import java.io.IOException;

import org.graphstream.algorithm.BellmanFord;
import org.graphstream.graph.Graph;
import org.graphstream.graph.implementations.DefaultGraph;
import org.graphstream.stream.file.FileSourceDGS;

public class BellmanFordTest {

//     B-(1)-C
//    /       \
//  (1)       (10)
//  /           \
// A             F
//  \           /
//  (1)       (1)
//    \       /
//     D-(1)-E
static String my_graph =
"DGS004\n"
+ "my 0 0\n"
+ "an A \n"
+ "an B \n"
+ "an C \n"
+ "an D \n"
+ "an E \n"
+ "an F \n"
+ "ae AB A B weight:1 \n"
+ "ae AD A D weight:1 \n"
+ "ae BC B C weight:1 \n"
+ "ae CF C F weight:10 \n"
+ "ae DE D E weight:1 \n"
+ "ae EF E F weight:1 \n"
;

public static void main(String[] args) throws IOException {
Graph graph = new DefaultGraph("Bellman-Ford Test");

FileSourceDGS source = new FileSourceDGS();

BellmanFord bf = new BellmanFord("weight","A");
bf.init(graph);
bf.compute();

System.out.println(bf.getShortestPath(graph.getNode("F")));
}
}
```

### Warning

This Implementation is only a stub. For the moment only attributes located on the edges are supported. If you need more features, consider using the Dijkstra implementation. If you really need that algorithm, please contact the team members through the mailing list.

Author:
Antoine Dutot, Yoann Pigné
Computational Complexity:
O(VxE) time, where V and E are the number of vertices and edges respectively.
Scientific Reference:
Bellman, Richard "On a routing problem", Quarterly of Applied Mathematics 16: 87–90. 1958.
• ### Field Summary

Fields
Modifier and Type Field and Description
`static java.lang.String` `DEFAULT_WEIGHT_ATTRIBUTE`
Default weight attribute
• ### Constructor Summary

Constructors
Constructor and Description
`BellmanFord()`
Build a new BellmanFord algorithm with default parameters.
`BellmanFord(java.lang.String attribute)`
Build a new BellmanFord algorithm giving the name of the weight attribute for edges.
```BellmanFord(java.lang.String attribute, java.lang.String sourceNode)```
Same that `BellmanFord(String)` but setting the id of the source node.
• ### Method Summary

All Methods
Modifier and Type Method and Description
`void` `compute()`
Run the algorithm.
`java.lang.String` `defaultResult()`
`java.lang.String` `getIdentifier()`
The unique identifier of this instance.
`java.util.List<org.graphstream.graph.Path>` `getPathSetShortestPaths(org.graphstream.graph.Node end)`
Constructs all the possible shortest paths from the source node to the destination (end).
`org.graphstream.graph.Path` `getShortestPath()`
`org.graphstream.graph.Path` `getShortestPath(org.graphstream.graph.Node target)`
Returns the shortest path between the source node and one given target.
`double` `getShortestPathValue(org.graphstream.graph.Node target)`
Returns the value of the shortest path between the source node and the given target according to the attribute specified in the constructor.
`java.lang.String` `getSource()`
Get the id of node used as source.
`void` `init(org.graphstream.graph.Graph graph)`
Initialization of the algorithm.
`void` `setIdentifier(java.lang.String identifier)`
Set the unique identifier for this instance.
`void` `setSource(java.lang.String nodeId)`
Set the id of the node used as source.
`void` `setTarget(java.lang.String target)`
`void` `setWeightAttribute(java.lang.String weightAttribute)`
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Field Detail

• #### DEFAULT_WEIGHT_ATTRIBUTE

`public static final java.lang.String DEFAULT_WEIGHT_ATTRIBUTE`
Default weight attribute
Constant Field Values
• ### Constructor Detail

• #### BellmanFord

`public BellmanFord()`
Build a new BellmanFord algorithm with default parameters.
• #### BellmanFord

`public BellmanFord(java.lang.String attribute)`
Build a new BellmanFord algorithm giving the name of the weight attribute for edges.
Parameters:
`attribute` - weight attribute of edges
• #### BellmanFord

```public BellmanFord(java.lang.String attribute,
java.lang.String sourceNode)```
Same that `BellmanFord(String)` but setting the id of the source node.
Parameters:
`attribute` - weight attribute of edges
`sourceNode` - id of the source node
• ### Method Detail

• #### setSource

`public void setSource(java.lang.String nodeId)`
Set the id of the node used as source.
Parameters:
`nodeId` - id of the source node
• #### setTarget

`public void setTarget(java.lang.String target)`
• #### setWeightAttribute

`public void setWeightAttribute(java.lang.String weightAttribute)`
• #### getSource

`public java.lang.String getSource()`
Get the id of node used as source.
Returns:
id of the source node
• #### getPathSetShortestPaths

`public java.util.List<org.graphstream.graph.Path> getPathSetShortestPaths(org.graphstream.graph.Node end)`
Constructs all the possible shortest paths from the source node to the destination (end). Warning: this construction is VERY HEAVY !
Parameters:
`end` - The destination to which shortest paths are computed.
Returns:
a list of shortest paths given with `Path` objects.
• #### init

`public void init(org.graphstream.graph.Graph graph)`
Description copied from interface: `Algorithm`
Initialization of the algorithm. This method has to be called before the `Algorithm.compute()` method to initialize or reset the algorithm according to the new given graph.
Specified by:
`init` in interface `Algorithm`
Parameters:
`graph` - The graph this algorithm is using.
• #### setIdentifier

`public void setIdentifier(java.lang.String identifier)`
Set the unique identifier for this instance.
Parameters:
`identifier` - the unique identifier to set
`getIdentifier()`
• #### getIdentifier

`public java.lang.String getIdentifier()`
The unique identifier of this instance. Used to tag attributes in the graph.
Returns:
the unique identifier of this graph.
• #### getShortestPathValue

`public double getShortestPathValue(org.graphstream.graph.Node target)`
Returns the value of the shortest path between the source node and the given target according to the attribute specified in the constructor. If `target` is not in the same connected component as the source node, then the method returns `Double.POSITIVE_INFINITY` (Infinity).
Parameters:
`target` - The endpoint of the path to compute from the source node given in the constructor.
Returns:
A numerical value that represent the distance of the shortest path.
• #### getShortestPath

`public org.graphstream.graph.Path getShortestPath(org.graphstream.graph.Node target)`
Returns the shortest path between the source node and one given target. If multiple shortest paths exist, one of them is returned at random.
Parameters:
`target` - the target of the shortest path starting at the source node given in the constructor.
Returns:
A `Path` object that constrains the list of nodes and edges that constitute it.
• #### defaultResult

`public java.lang.String defaultResult()`
• #### compute

`public void compute()`
Description copied from interface: `Algorithm`
Run the algorithm. The `Algorithm.init(Graph)` method has to be called before computing.
Specified by:
`compute` in interface `Algorithm`
`Algorithm.init(Graph)`