# pgRouting Manual (3.6)

## Cost Matrix - Category

- pgr_aStarCostMatrix

- pgr_bdAstarCostMatrix

- pgr_bdDijkstraCostMatrix

- pgr_dijkstraCostMatrix

- pgr_bdDijkstraCostMatrix

proposed

Warning

Proposed functions for next mayor release.

- They are not officially in the current release.

- They will likely officially be part of the next mayor release:

  - The functions make use of ANY-INTEGER and ANY-NUMERICAL

  - Name might not change. (But still can)

  - Signature might not change. (But still can)

  - Functionality might not change. (But still can)

  - pgTap tests have being done. But might need more.

  - Documentation might need refinement.

- pgr_withPointsCostMatrix - proposed

## General Information

### Synopsis

Traveling Sales Person - Family of functions needs as input a symmetric cost matrix and no edge (u, v) must value \(\infty\).

This collection of functions will return a cost matrix in form of a table.

### Characteristics

The main Characteristics are:

- Can be used as input to pgr_TSP.

  - Use directly when the resulting matrix is symmetric and there is no \(\infty\) value.

  - It will be the users responsibility to make the matrix symmetric.

    - By using geometric or harmonic average of the non symmetric values.

    - By using max or min the non symmetric values.

    - By setting the upper triangle to be the mirror image of the lower triangle.

    - By setting the lower triangle to be the mirror image of the upper triangle.

  - It is also the users responsibility to fix an \(\infty\) value.

- Each function works as part of the family it belongs to.

- It does not return a path.

- Returns the sum of the costs of the shortest path for pair combination of nodes in the graph.

- Process is done only on edges with positive costs.

- Values are returned when there is a path.

  - When the starting vertex and ending vertex are the same, there is no path.

    - The aggregate cost in the non included values (v, v) is 0.

  - When the starting vertex and ending vertex are the different and there is no path.

    - The aggregate cost in the non included values (u, v) is \(\infty\).

- Let be the case the values returned are stored in a table:

  - The unique index would be the pair: `(start_vid, end_vid)`.

- Depending on the function and its parameters, the results can be symmetric.

  - The aggregate cost of (u, v) is the same as for (v, u).

- Any duplicated value in the start vids are ignored.

- The returned values are ordered:

  - `start_vid` ascending

  - `end_vid` ascending

## Parameters

Used in:

- pgr_aStarCostMatrix

- pgr_dijkstraCostMatrix

Column | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | Edges SQL as described below
start vids | `ARRAY[BIGINT]` | Array of identifiers of starting vertices.

Used in:

- pgr_withPointsCostMatrix - proposed

Column | Type | Description
--- | --- | ---
Edges SQL | `TEXT` | Edges SQL as described below
Points SQL | `TEXT` | Points SQL as described below
start vids | `ARRAY[BIGINT]` | Array of identifiers of starting vertices.

### Optional parameters

Column | Type | Default | Description
--- | --- | --- | ---

`directed`

`BOOLEAN`

`true`

- When `true` the graph is considered Directed

- When `false` the graph is considered as Undirected.

## Inner Queries

### Edges SQL

Used in:

- pgr_withPointsCostMatrix - proposed

- pgr_dijkstraCostMatrix

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`

### Points SQL

Parameter | Type | Default | Description
--- | --- | --- | ---

`pid`

ANY-INTEGER

value

Identifier of the point.

- Use with positive value, as internally will be converted to negative value

- If column is present, it can not be NULL.

- If column is not present, a sequential negative value will be given automatically.

`edge_id` | ANY-INTEGER |  | Identifier of the “closest” edge to the point.
`fraction` | ANY-NUMERICAL |  | Value in <0,1> that indicates the relative postition from the first end point of the edge.

`side`

`CHAR`

`b`

Value in [`b`, `r`, `l`, `NULL`] indicating if the point is:

- In the right `r`,

- In the left `l`,

- In both sides `b`, `NULL`

Where:

ANY-INTEGER:

  `SMALLINT`, `INTEGER`, `BIGINT`

ANY-NUMERICAL:

  `SMALLINT`, `INTEGER`, `BIGINT`, `REAL`, `FLOAT`

## Result columns

Set of `(start_vid, end_vid, agg_cost)`

Column | Type | Description
--- | --- | ---
`start_vid` | `BIGINT` | Identifier of the starting vertex.
`end_vid` | `BIGINT` | Identifier of the ending vertex.
`agg_cost` | `FLOAT` | Aggregate cost from `start_vid` to `end_vid`.

## See Also

- Traveling Sales Person - Family of functions

Indices and tables

- Index

- Search Page