pgr_apspWarshall - Plus court chemin toutes paires, Algorithme Floyd-Warshall¶

Nom¶

pgr_apspWarshall - Retourne tous les coûts pour chaque paire de noeuds dans le graphe.

Synopsis¶

The Floyd-Warshall algorithm (also known as Floyd’s algorithm and other names) is a graph analysis algorithm for finding the shortest paths between all pairs of nodes in a weighted graph. Returns a set of pgr_costResult (seq, id1, id2, cost) rows for every pair of nodes in the graph.

pgr_costResult[] pgr_apspWarshall(sql text, directed boolean, reverse_cost boolean);

Description¶

sql:

une requête SQL qui maintient les arêtes pour le graphe qui sera analysé :

SELECT source, target, cost FROM edge_table;

id:	`int4` identifiant de l’arête
source:	`int4` identifiant du sommet source pour cette arête
target:	`int4` identifiant du sommet cible pour cette arête
cost:	`float8` une valeur positive pour le coût pour traverser cette arête

directed:

true si le graphe est dirigé

reverse_cost:

si true, la colonne reverse_cost du SQL générant l’ensemble des lignes va être utilisé pour le coût de la traversée de l’arête dans la direction opposée.

Retourne un ensemble de pgr_costResult[]:

seq:	séquence de ligne
id1:	ID noeud source
id2:	ID nœud cible
cost:	coût pour traverser de `id1` en utilisant `id2`

Histoire

Nouveau depuis la version 2.0.0

Exemples¶

SELECT seq, id1 AS from, id2 AS to, cost
    FROM pgr_apspWarshall(
        'SELECT id, source, target, cost FROM edge_table',
        false, false
    );

 seq | from | to | cost
-----+------+----+------
   0 |    1 |  1 |    0
   1 |    1 |  2 |    1
   2 |    1 |  3 |    0
   3 |    1 |  4 |   -1
[...]

La requête utilise le réseau Données d’échantillon.

pgRouting Manual (2.0.0)