Bellman-Ford Algorithm
Introduction
The Bellman-Ford algorithm finds the path with the lowest total edge weight from a source node, like Dijkstra's algorithm, but it also accepts negative edge weights. With a sink, it returns the shortest path to that node. Without one, it returns the shortest path to every node the source can reach.
If the source can reach a cycle whose total weight is negative, paths through that cycle have no shortest length, and the run fails with Graph contains a negative cycle. A negative cycle that the source cannot reach does not affect the run. The program follows edges in their stored direction only. On graphs without negative weights, Dijkstra's algorithm is faster.
Run Bellman-Ford from Cypher with CALL algo.shortestpath.bellmanFord, or from Gremlin with LocalBellmanFordShortestPathProgram. See Shortest Paths for how to run it, the output fields, the arguments shared by all shortest path algorithms, and sizing guidance.
Query Examples
Shortest path between two nodes
The shortest path from marko (person[v1]) to lop (software[v3]) in the Modern example graph:
CALL algo.shortestpath.bellmanFord({
labels: ['person', 'software'],
relationshipTypes: ['knows', 'created'],
relationshipWeightProperty: 'weight',
sourceNode: 'person[v1]',
targetNode: 'software[v3]'
}) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight
Output:
Negative edge weights
The Modern graph has no negative weights, so this example subtracts 0.6 from every edge with fixedPenalty(-0.6). Edges lighter than 0.6, such as created[e9], then have a negative weight. Dijkstra's algorithm rejects this graph, and Bellman-Ford returns:
CALL algo.shortestpath.bellmanFord({
labels: ['person', 'software'],
relationshipTypes: ['knows', 'created'],
relationshipWeightProperty: 'weight',
fixedPenalty: -0.6,
sourceNode: 'person[v1]',
targetNode: 'software[v3]'
}) YIELD vertexList, edgeList, weight
RETURN vertexList, edgeList, weight
Output:
Weights are floating-point numbers, so a sum can show a rounding error, as here (0.4 - 0.6).
Parameters
| Cypher argument | Gremlin method | Description | Required | Default Value |
|---|---|---|---|---|
sourceNode |
source(String id) |
The ID of the node to start from | Yes | |
targetNode |
sink(String id) |
The ID of the target node. Without it, the program returns a path to every reachable node | No | |
relationshipWeightProperty |
weightProperty(String name) |
The edge property to use as the weight | Yes |
The common arguments also apply.