As a follow up from 1-center and k-center problem / maxmin facility problem in Post
I have a strange behavior for the Floyd-Warshall algorithm which seems to give not all pairs. Why are so many pairs missing?
I took the following steps:
- Create a topology from my vertices using pgr_CreateTopology (gives me a network with 5700 vertices and corresponding start and end ids.
- Run Floyd-Warshall, end up with 157.000 pairs (in contrast to 5700 * (5700 - 1) = 32 Mio.
- Analyze number of pairs calculated -> lowest pair count is 1 pair
E.g. for source node 1481: Gives only 2 pairs, i.e. the source node 1481 (which is close to the end of the graph) is only listed with costs to itself (1481 <-> 1481) and between (1481 <-> 1476). The later is the end node of the vertex which connects 1481 and 1476.
The output from pgr_analyzeGraph():
NOTICE: Performing checks, please wait ...
NOTICE: Analyzing for dead ends. Please wait...
NOTICE: Analyzing for gaps. Please wait...
NOTICE: Analyzing for isolated edges. Please wait...
NOTICE: Analyzing for ring geometries. Please wait...
NOTICE: Analyzing for intersections. Please wait...
NOTICE: ANALYSIS RESULTS FOR SELECTED EDGES:
NOTICE: Isolated segments: 6
NOTICE: Dead ends: 1046
NOTICE: Potential gaps found near dead ends: 0
NOTICE: Intersections detected: 197
NOTICE: Ring geometries: 3
From the docs:
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.
The sample data provided by pgrouting shows the same behavior: Take e.g. node 17. Running pgrouting's Floyd-Warshall returns one row, connecting 17 <-> 16. This is not what I would understand under "all pairs". Can someone shed some light on my misunderstandings?