Skip navigation links
WebARTS Design
Java Library

Version 0.10.2
2020-11-11 (Wed), 10:42:54
org.graphstream.algorithm

## Class BellmanFord

• All Implemented Interfaces:
Algorithm

```public class BellmanFord
extends 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 java.io.StringReader;

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");
StringReader reader  = new StringReader(my_graph);

FileSourceDGS source = new FileSourceDGS();
source.addSink(graph);
source.readAll(reader);

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é
• ### Field Summary

Fields
Modifier and Type Field and Description
`protected Graph` `graph`
The graph to be computed for shortest path.
`protected String` `identifier`
object-level unique string that identifies tags of this instance on a graph.
`protected Node` `source`
`protected String` `source_id`
ID of the source node.
`protected String` `weightAttribute`
Name of attribute used to get weight of edges.
• ### Constructor Summary

Constructors
Constructor and Description
`BellmanFord(String attribute)`
Build a new BellmanFord algorithm giving the name of the weight attribute for edges.
```BellmanFord(String attribute, 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.
`String` `getIdentifier()`
The unique identifier of this instance.
`List<Path>` `getPathSetShortestPaths(Node end)`
Constructs all the possible shortest paths from the source node to the destination (end).
`Path` `getShortestPath(Node target)`
Returns the shortest path between the source node and one given target.
`double` `getShortestPathValue(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.
`String` `getSource()`
Get the id of node used as source.
`void` `init(Graph graph)`
Initialization of the algorithm.
`private void` ```pathSetShortestPath_facilitate(Node current, Path path, List<Path> paths)```
`void` `setIdentifier(String identifier)`
Set the unique identifier for this instance.
`void` `setSource(String nodeId)`
Set the id of the node used as source.
• ### Methods inherited from class java.lang.Object

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

• #### graph

`protected Graph graph`
The graph to be computed for shortest path.
• #### source_id

`protected String source_id`
ID of the source node.
• #### source

`protected Node source`
• #### identifier

`protected String identifier`
object-level unique string that identifies tags of this instance on a graph.
• #### weightAttribute

`protected String weightAttribute`
Name of attribute used to get weight of edges.
• ### Constructor Detail

• #### BellmanFord

`public BellmanFord(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(String attribute,
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(String nodeId)`
Set the id of the node used as source.
Parameters:
`nodeId` - id of the source node
• #### getSource

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

`public List<Path> getPathSetShortestPaths(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.
• #### pathSetShortestPath_facilitate

```private void pathSetShortestPath_facilitate(Node current,
Path path,
List<Path> paths)```
• #### init

`public void init(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(String identifier)`
Set the unique identifier for this instance.
Parameters:
`identifier` - the unique identifier to set
See Also:
`getIdentifier()`
• #### getIdentifier

`public 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(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 Path getShortestPath(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.
• #### 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`
See Also:
`Algorithm.init(Graph)`
Skip navigation links
Copyright (C) 2001-2021, Tom B. Gutwin

WebARTS Library Licensed Under the GNU - General Public License. Other Libraries licensed under their respective Open Source Licenses