Skip to content

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:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "weight": 0.4
  }
]
graph.program(
  LocalBellmanFordShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .source("person[v1]")
    .sink("software[v3]")
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "edgeResultList": [{"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}],
    "weight": 0.4
  }
]

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:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "weight": -0.19999999999999996
  }
]
graph.program(
  LocalBellmanFordShortestPathProgram.build()
    .vertices("person", "software")
    .edges("knows", "created")
    .weightProperty("weight")
    .fixedPenalty(-0.6)
    .source("person[v1]")
    .sink("software[v3]")
    .create()
).submitAndGetLocal().getMapResult()

Output:

[
  {
    "vertexList": ["person[v1]", "software[v3]"],
    "edgeList": ["created[e9]"],
    "edgeResultList": [{"id": "created[e9]", "from": "person[v1]", "to": "software[v3]"}],
    "weight": -0.19999999999999996
  }
]

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.