Navigation :

Table of Contents - pgRouting Manual (3.4) > pgr_dagShortestPath - Experimental - pgRouting Manual (3.4)

pgr_dagShortestPath - Experimental - pgRouting Manual (3.4)

Supported versions: Latest ( 3.4 ) 3.3 3.2 3.1 3.0

pgr_dagShortestPath - Experimental

pgr_dagShortestPath - Returns the shortest path(s) for weighted directed acyclic graphs(DAG). In particular, the DAG shortest paths algorithm implemented by Boost.Graph.

images/boost-inside.jpeg — Boost Graph Inside

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 function:
  - pgr_dagShortestPath(Combinations)
Version 3.0.0
- New experimental function

Description

Shortest Path for Directed Acyclic Graph(DAG) is a graph search algorithm that solves the shortest path problem for weighted directed acyclic graph, producing a shortest path from a starting vertex ( start_vid ) to an ending vertex ( end_vid ).

This implementation can only be used with a directed graph with no cycles i.e. directed acyclic graph.

The algorithm relies on topological sorting the dag to impose a linear ordering on the vertices, and thus is more efficient for DAG’s than either the Dijkstra or Bellman-Ford algorithm.

The main characteristics are:

Process is valid for weighted directed acyclic graphs only. otherwise it will throw warnings.
Values are returned when there is a path.
- When the starting vertex and ending vertex are the same, there is no path.
  - The agg_cost the non included values (v, v) is 0
- When the starting vertex and ending vertex are the different and there is no path:
  - The agg_cost the non included values (u, v) 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

      pgr_dagShortestPath(
      
       Edges SQL
      
      ,
      
       start vid
      
      ,
      
       end vid
      
      )
     
      pgr_dagShortestPath(
      
       Edges SQL
      
      ,
      
       start vid
      
      ,
      
       end vids
      
      )
     
      pgr_dagShortestPath(
      
       Edges SQL
      
      ,
      
       start vids
      
      ,
      
       end vid
      
      )
     
      pgr_dagShortestPath(
      
       Edges SQL
      
      ,
      
       start vids
      
      ,
      
       end vids
      
      )
     
      pgr_dagShortestPath(
      
       Edges SQL
      
      ,
      
       Combinations SQL
      
      )

RETURNS SET OF


       
        (seq,
       
       
        path_seq,
       
       
        node,
       
       
        edge,
       
       
        cost,
       
       
        agg_cost)

OR EMPTY SET

One to One

pgr_dagShortestPath( Edges SQL , start vid , end vid )

RETURNS SET OF

OR EMPTY SET

Example :: From vertex \(5\) to vertex \(11\) on a directed graph

      SELECT * FROM pgr_dagShortestPath(
  'SELECT id, source, target, cost FROM edges',
  5, 11);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     5     1     1         0
   2         2     6     4     1         1
   3         3     7     8     1         2
   4         4    11    -1     0         3
(4 rows)


     

One to Many

pgr_dagShortestPath( Edges SQL , start vid , end vids )

RETURNS SET OF

OR EMPTY SET

Example :: From vertex \(5\) to vertices \(\{7, 11\}\)

      SELECT * FROM pgr_dagShortestPath(
  'SELECT id, source, target, cost FROM edges',
  5, ARRAY[7, 11]);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     5     1     1         0
   2         2     6     4     1         1
   3         3     7    -1     0         2
   4         1     5     1     1         0
   5         2     6     4     1         1
   6         3     7     8     1         2
   7         4    11    -1     0         3
(7 rows)


     

Many to One

pgr_dagShortestPath( Edges SQL , start vids , end vid )

RETURNS SET OF

OR EMPTY SET

Example :: From vertices \(\{5, 10\}\) to vertex \(11\)

      SELECT * FROM pgr_dagShortestPath(
  'SELECT id, source, target, cost FROM edges',
  ARRAY[5, 10], 11);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     5     1     1         0
   2         2     6     4     1         1
   3         3     7     8     1         2
   4         4    11    -1     0         3
   5         1    10     5     1         0
   6         2    11    -1     0         1
(6 rows)


     

Many to Many

pgr_dagShortestPath( Edges SQL , start vids , end vids )

RETURNS SET OF

OR EMPTY SET

Example :: From vertices \(\{5, 15\}\) to vertices \(\{11, 17\}\) on an undirected graph

      SELECT * FROM pgr_dagShortestPath(
  'SELECT id, source, target, cost FROM edges',
  ARRAY[5, 15], ARRAY[11, 17]);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     5     1     1         0
   2         2     6     4     1         1
   3         3     7     8     1         2
   4         4    11    -1     0         3
   5         1     5     1     1         0
   6         2     6     4     1         1
   7         3     7     8     1         2
   8         4    11     9     1         3
   9         5    16    15     1         4
  10         6    17    -1     0         5
  11         1    15    16     1         0
  12         2    16    15     1         1
  13         3    17    -1     0         2
(13 rows)


     

Combinations

pgr_dagShortestPath( Edges SQL , Combinations SQL )

RETURNS SET OF

OR EMPTY SET

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_dagShortestPath(
  'SELECT id, source, target, cost FROM edges',
  'SELECT source, target FROM combinations');
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     5     1     1         0
   2         2     6    -1     0         1
(2 rows)


     

Parameters

Column	Type	Description
Edges SQL	`TEXT`	Edges SQL as described below
Combinations SQL	`TEXT`	Combinations SQL as described below
start vid	`BIGINT`	Identifier of the starting vertex of the path.
start vids	`ARRAY[BIGINT]`	Array of identifiers of starting vertices.
end vid	`BIGINT`	Identifier of the ending vertex of the path.
end vids	`ARRAY[BIGINT]`	Array of identifiers of ending vertices.

Inner Queries

Edges SQL

Column	Type	Default	Description
`id`	ANY-INTEGER		Identifier of the edge.
`source`	ANY-INTEGER		Identifier of the first end point vertex of the edge.
`target`	ANY-INTEGER		Identifier of the second end point vertex of the edge.
`cost`	ANY-NUMERICAL		Weight of the edge ( `source` , `target` )
`reverse_cost`	ANY-NUMERICAL	-1	Weight of the edge ( `target` , `source` ) When negative: edge ( `target` , `source` ) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER :: SMALLINT , INTEGER , BIGINT
ANY-NUMERICAL :: SMALLINT , INTEGER , BIGINT , REAL , FLOAT

Combinations SQL

Parameter	Type	Description
`source`	ANY-INTEGER	Identifier of the departure vertex.
`target`	ANY-INTEGER	Identifier of the arrival vertex.

Where:

ANY-INTEGER :: SMALLINT , INTEGER , BIGINT

Resturn Columns

Returns set of (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Column	Type	Description
`seq`	`INTEGER`	Sequential value starting from 1 .
`path_seq`	`INTEGER`	Relative position in the path. Has value 1 for the beginning of a path.
`start_vid`	`BIGINT`	Identifier of the starting vertex. Returned when multiple starting vetrices are in the query. Many to One Many to Many
`end_vid`	`BIGINT`	Identifier of the ending vertex. Returned when multiple ending vertices are in the query. One to Many Many to Many
`node`	`BIGINT`	Identifier of the node in the path from `start_vid` to `end_vid` .
`edge`	`BIGINT`	Identifier of the edge used to go from `node` to the next node in the path sequence. -1 for the last node of the path.
`cost`	`FLOAT`	Cost to traverse from `node` using `edge` to the next node in the path sequence.
`agg_cost`	`FLOAT`	Aggregate cost from `start_vid` to `node` .

Additional Examples

Example 1 :: Demonstration of repeated values are ignored, and result is sorted.

     SELECT * FROM pgr_dagShortestPath(
  'SELECT id, source, target, cost FROM edges',
  ARRAY[5, 10, 5, 10, 10, 5], ARRAY[11, 17, 17, 11]);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
       1     5     1     1         0
       2     6     4     1         1
       3     7     8     1         2
       4    11    -1     0         3
       1     5     1     1         0
       2     6     4     1         1
       3     7     8     1         2
       4    11     9     1         3
       5    16    15     1         4
       6    17    -1     0         5
       1    10     5     1         0
       2    11    -1     0         1
       1    10     5     1         0
       2    11     9     1         1
       3    16    15     1         2
       4    17    -1     0         3
(16 rows)


    

Example 2 :: Making start_vids the same as end_vids

     SELECT * FROM pgr_dagShortestPath(
  'SELECT id, source, target, cost FROM edges',
  ARRAY[5, 10, 11], ARRAY[5, 10, 11]);
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     5     1     1         0
   2         2     6     4     1         1
   3         3     7     8     1         2
   4         4    11    -1     0         3
   5         1    10     5     1         0
   6         2    11    -1     0         1
(6 rows)


    

Example 3 :: Manually assigned vertex combinations.

     SELECT * FROM pgr_dagShortestPath(
  'SELECT id, source, target, cost FROM edges',
  'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
 seq  path_seq  node  edge  cost  agg_cost
-----+----------+------+------+------+----------
   1         1     6     4     1         0
   2         2     7    -1     0         1
(2 rows)


    

pgr_dagShortestPath - Experimental - pgRouting Manual (3.4)