pgRouting Manual (2.0.0)

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

«  pgr_apspJohnson - Plus court chemin toutes paires, algorithme de Johnson   ::   Contenu   ::   pgr_astar - Plus court chemin A*  »

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.

«  pgr_apspJohnson - Plus court chemin toutes paires, algorithme de Johnson   ::   Contenu   ::   pgr_astar - Plus court chemin A*  »