1

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?

The Details:

I took the following steps:

  1. Create a topology from my vertices using pgr_CreateTopology (gives me a network with 5700 vertices and corresponding start and end ids.
  2. Run Floyd-Warshall, end up with 157.000 pairs (in contrast to 5700 * (5700 - 1) = 32 Mio.
  3. 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: PROCESSING:

NOTICE: pgr_analyzeGraph('network',0.1,'the_geom','gid','start_id','end_id','true')

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?

  • As far as the example goes, nodes 16 and 17 are only connected to each other. Look at the example diagram: where edge 16-17 crosses edge 11-12, there is no node. So the example does return all possible pairs. – Richard Law Feb 5 '16 at 18:56
  • Ok, I am wrong. I checked the algorithm at Wikipedia. I apologize for not doing this before - was a long day... So, the algorithm returns only the pairs which are still unknown. Thus, all pairs and ways until node 15 are already calculated. The missing path is only 16 to 17. That explains the efficiency in storing all paths. – Frank Feb 5 '16 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.