pgr_bellmanFord - Experimental - pgRouting Manual (3.3)
pgr_bellmanFord
-
Experimental
pgr_bellmanFord
- Shortest path(s) using Bellman-Ford algorithm.
Warning
Possible server crash
-
These functions might create a server crash
Warning
Experimental functions
-
They are not officially of the current release.
-
They likely will not be officially be part of the next release:
-
The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
-
Name might change.
-
Signature might change.
-
Functionality might change.
-
pgTap tests might be missing.
-
Might need c/c++ coding.
-
May lack documentation.
-
Documentation if any might need to be rewritten.
-
Documentation examples might need to be automatically generated.
-
Might need a lot of feedback from the comunity.
-
Might depend on a proposed function of pgRouting
-
Might depend on a deprecated function of pgRouting
-
Availability
-
Version 3.2.0
-
New experimental signature:
-
pgr_bellmanFord( Combinations )
-
-
-
Version 3.0.0
-
New experimental signatures:
-
pgr_bellmanFord( One to One ) -
pgr_bellmanFord( One to Many ) -
pgr_bellmanFord( Many to One ) -
pgr_bellmanFord( Many to Many )
-
-
Description
Bellman-Ford’s algorithm, is named after Richard Bellman and Lester Ford, who
first published it in 1958 and 1956, respectively.It is a graph search algorithm
that computes shortest paths from a starting vertex (
start_vid
) to an ending
vertex (
end_vid
) in a graph where some of the edge weights may be negative.
Though it is more versatile, it is slower than Dijkstra’s algorithm.This
implementation can be used with a directed graph and an undirected graph.
- The main characteristics are:
-
-
Process is valid for edges with both positive and negative edge weights.
-
Values are returned when there is a path.
-
When the start vertex and the end vertex are the same, there is no path. The agg_cost would be \(0\) .
-
When the start vertex and the end vertex are different, and there exists a path between them without having a negative cycle . The agg_cost would be some finite value denoting the shortest distance between them.
-
When the start vertex and the end vertex are different, and there exists a path between them, but it contains a negative cycle . In such case, agg_cost for those vertices keep on decreasing furthermore, Hence agg_cost can’t be defined for them.
-
When the start vertex and the end vertex are different, and there is no path. The agg_cost is \(\infty\) .
-
-
For optimization purposes, any duplicated value in the start_vids or end_vids are ignored.
-
The returned values are ordered:
-
start_vid ascending
-
end_vid ascending
-
-
Running time: \(O( start\_vids * ( V * E))\)
-
Signatures
Summary
directed
])
directed
])
directed
])
directed
])
(seq,
path_seq,
[start_vid],
[end_vid],
node,
edge,
cost,
agg_cost)
One to One
directed
])
(seq,
path_seq,
node,
edge,
cost,
agg_cost)
- Example :
-
From vertex \(6\) to vertex \(10\) on a directed graph
SELECT * FROM pgr_bellmanFord(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 10, true);
seq path_seq node edge cost agg_cost
-----+----------+------+------+------+----------
1 1 6 4 1 0
2 2 7 8 1 1
3 3 11 9 1 2
4 4 16 16 1 3
5 5 15 3 1 4
6 6 10 -1 0 5
(6 rows)
One to Many
directed
])
(seq,
path_seq,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
From vertex \(6\) to vertices \(\{ 10, 17\}\) on a directed graph
SELECT * FROM pgr_bellmanFord(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, ARRAY[10, 17]);
seq path_seq end_vid node edge cost agg_cost
-----+----------+---------+------+------+------+----------
1 1 10 6 4 1 0
2 2 10 7 8 1 1
3 3 10 11 9 1 2
4 4 10 16 16 1 3
5 5 10 15 3 1 4
6 6 10 10 -1 0 5
7 1 17 6 4 1 0
8 2 17 7 8 1 1
9 3 17 11 11 1 2
10 4 17 12 13 1 3
11 5 17 17 -1 0 4
(11 rows)
Many to One
directed
])
(seq,
path_seq,
start_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
From vertices \(\{6, 1\}\) to vertex \(17\) on a directed graph
SELECT * FROM pgr_bellmanFord(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 1], 17);
seq path_seq start_vid node edge cost agg_cost
-----+----------+-----------+------+------+------+----------
1 1 1 1 6 1 0
2 2 1 3 7 1 1
3 3 1 7 8 1 2
4 4 1 11 11 1 3
5 5 1 12 13 1 4
6 6 1 17 -1 0 5
7 1 6 6 4 1 0
8 2 6 7 8 1 1
9 3 6 11 11 1 2
10 4 6 12 13 1 3
11 5 6 17 -1 0 4
(11 rows)
Many to Many
directed
])
(seq,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
From vertices \(\{6, 1\}\) to vertices \(\{10, 17\}\) on an undirected graph
SELECT * FROM pgr_bellmanFord(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 1], ARRAY[10, 17],
directed => false);
seq path_seq start_vid end_vid node edge cost agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 1 1 10 1 6 1 0
2 2 1 10 3 7 1 1
3 3 1 10 7 4 1 2
4 4 1 10 6 2 1 3
5 5 1 10 10 -1 0 4
6 1 1 17 1 6 1 0
7 2 1 17 3 7 1 1
8 3 1 17 7 8 1 2
9 4 1 17 11 11 1 3
10 5 1 17 12 13 1 4
11 6 1 17 17 -1 0 5
12 1 6 10 6 2 1 0
13 2 6 10 10 -1 0 1
14 1 6 17 6 4 1 0
15 2 6 17 7 8 1 1
16 3 6 17 11 11 1 2
17 4 6 17 12 13 1 3
18 5 6 17 17 -1 0 4
(18 rows)
Combinations
(seq,
path_seq,
start_vid,
end_vid,
node,
edge,
cost,
agg_cost)
- Example :
-
Using a combinations table on an undirected graph.
The combinations table:
SELECT source, target FROM combinations;
source target
--------+--------
5 6
5 10
6 5
6 15
6 14
(5 rows)
The query:
SELECT * FROM pgr_bellmanFord(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations',
false);
seq path_seq start_vid end_vid node edge cost agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 1 5 6 5 1 1 0
2 2 5 6 6 -1 0 1
3 1 5 10 5 1 1 0
4 2 5 10 6 2 1 1
5 3 5 10 10 -1 0 2
6 1 6 5 6 1 1 0
7 2 6 5 5 -1 0 1
8 1 6 15 6 2 1 0
9 2 6 15 10 3 1 1
10 3 6 15 15 -1 0 2
(10 rows)
Parameters
|
Column |
Type |
Description |
|---|---|---|
|
|
Edges SQL as described below |
|
|
|
Combinations SQL as described below |
|
|
start vid |
|
Identifier of the starting vertex of the path. |
|
start vids |
|
Array of identifiers of starting vertices. |
|
end vid |
|
Identifier of the ending vertex of the path. |
|
end vids |
|
Array of identifiers of ending vertices. |
Optional parameters
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
|
|
|
Inner Queries
Edges SQL
|
Column |
Type |
Default |
Description |
|---|---|---|---|
|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
|
ANY-NUMERICAL |
Weight of the edge (
|
|
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT - ANY-NUMERICAL :
-
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Combinations SQL
|
Parameter |
Type |
Description |
|---|---|---|
|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Where:
- ANY-INTEGER :
-
SMALLINT,INTEGER,BIGINT
Return columns
Returns set of
(seq,
path_seq
[,
start_vid]
[,
end_vid],
node,
edge,
cost,
agg_cost)
|
Column |
Type |
Description |
|---|---|---|
|
|
|
Sequential value starting from 1 . |
|
|
|
Relative position in the path. Has value 1 for the beginning of a path. |
|
|
|
Identifier of the starting vertex. Returned when multiple starting vetrices are in the query. |
|
|
|
Identifier of the ending vertex. Returned when multiple ending vertices are in the query. |
|
|
|
Identifier of the node in the path from
|
|
|
|
Identifier of the edge used to go from
|
|
|
|
Cost to traverse from
|
|
|
|
Aggregate cost from
|
Additional Examples
- Example 1 :
-
Demonstration of repeated values are ignored, and result is sorted.
SELECT * FROM pgr_bellmanFord(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[7, 10, 15, 10, 10, 15], ARRAY[10, 7, 10, 15]);
seq path_seq start_vid end_vid node edge cost agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 1 7 10 7 8 1 0
2 2 7 10 11 9 1 1
3 3 7 10 16 16 1 2
4 4 7 10 15 3 1 3
5 5 7 10 10 -1 0 4
6 1 7 15 7 8 1 0
7 2 7 15 11 9 1 1
8 3 7 15 16 16 1 2
9 4 7 15 15 -1 0 3
10 1 10 7 10 5 1 0
11 2 10 7 11 8 1 1
12 3 10 7 7 -1 0 2
13 1 10 15 10 5 1 0
14 2 10 15 11 9 1 1
15 3 10 15 16 16 1 2
16 4 10 15 15 -1 0 3
17 1 15 7 15 3 1 0
18 2 15 7 10 2 1 1
19 3 15 7 6 4 1 2
20 4 15 7 7 -1 0 3
21 1 15 10 15 3 1 0
22 2 15 10 10 -1 0 1
(22 rows)
- Example 2 :
-
Making start vids the same as end vids .
SELECT * FROM pgr_bellmanFord(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
seq path_seq start_vid end_vid node edge cost agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 1 7 10 7 8 1 0
2 2 7 10 11 9 1 1
3 3 7 10 16 16 1 2
4 4 7 10 15 3 1 3
5 5 7 10 10 -1 0 4
6 1 7 15 7 8 1 0
7 2 7 15 11 9 1 1
8 3 7 15 16 16 1 2
9 4 7 15 15 -1 0 3
10 1 10 7 10 5 1 0
11 2 10 7 11 8 1 1
12 3 10 7 7 -1 0 2
13 1 10 15 10 5 1 0
14 2 10 15 11 9 1 1
15 3 10 15 16 16 1 2
16 4 10 15 15 -1 0 3
17 1 15 7 15 3 1 0
18 2 15 7 10 2 1 1
19 3 15 7 6 4 1 2
20 4 15 7 7 -1 0 3
21 1 15 10 15 3 1 0
22 2 15 10 10 -1 0 1
(22 rows)
- Example 3 :
-
Manually assigned vertex combinations.
SELECT * FROM pgr_bellmanFord(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
seq path_seq start_vid end_vid node edge cost agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 1 6 7 6 4 1 0
2 2 6 7 7 -1 0 1
3 1 6 10 6 4 1 0
4 2 6 10 7 8 1 1
5 3 6 10 11 9 1 2
6 4 6 10 16 16 1 3
7 5 6 10 15 3 1 4
8 6 6 10 10 -1 0 5
9 1 12 10 12 13 1 0
10 2 12 10 17 15 1 1
11 3 12 10 16 16 1 2
12 4 12 10 15 3 1 3
13 5 12 10 10 -1 0 4
(13 rows)
See Also
Indices and tables