Ticket #88 (new bug report)

Opened 3 years ago

Last modified 14 months ago

Dijkstra crashes if a cost is negative

Reported by: Tristram Owned by: somebody
Priority: critical Milestone:
Component: Dijkstra Version: 1.0
Keywords: Cc:


According to the documentation :

- cost: double precision value of the edge traversal cost. (a negative cost
   will prevent the edge from being inserted in the graph).

Yet when I have a negative cost (-1) to forbid using an edge it seems to crash (I don't know what really happens :

testdb=# SELECT * FROM shortest_path('SELECT edge_id AS id, source_id::int4 as source,  target_id::int4 as target, cost::double precision AS cost FROM streets_topology',18342, 49625, false, false);
server closed the connection unexpectedly
        This probably means the server terminated abnormally
        before or while processing the request.
The connection to the server was lost. Attempting reset: Failed.

If I set the cost to a high value, or 'Infinity' it works correctly.

I suppose that the algorithm considers that the edge exists and has a negative cost (which is a problem with Dijkstra).

Change History

Changed 3 years ago by Tristram

Whoops! I forgot to give my setup : Ubuntu Gusty on Intel Core2 Duo

Postgres version 8.2.5-1.1 (standard Ubuntu package) Postgis version 1.2.1-2 (standard Ubuntu package) pgRouting 1.0.0 from tarball (installation through cmake .; make)

The data base is a subset of Navteq's Streets (180K edges) and the topology created with assign_vertex_id

Changed 3 years ago by Tristram

Hello again

My assumption might be wrong : I have an other crash happening with all the cost positive (and not null). As vertex_id I used my own data. Those vertex_id can be quite big (the biggest is 724138634) but I don't think it's the cause as it's only 230 bits big (while the C code seems to use int that are from -231 to 231 on my machine).

Where should I look to get more informations (how could I trace the crash ?), and what information could help you ?

Thank you !

Changed 14 months ago by fredj

Same issue here with pgRouting 1.03, postgresql 8.3 and boost 1.35. Postgresql error log:

terminate called after throwing an instance of 'boost::negative_edge'
  what():  The graph may not contain an edge with negative weight.
2009-10-08 12:44:20 CEST LOG:  server process (PID 13888) was terminated by signal 6: Aborted
2009-10-08 12:44:20 CEST LOG:  terminating any other active server processes
2009-10-08 12:44:20 CEST LOG:  all server processes terminated; reinitializing
2009-10-08 12:44:20 CEST LOG:  database system was interrupted; last known up at 2009-10-08 12:43:24 CEST
2009-10-08 12:44:20 CEST LOG:  database system was not properly shut down; automatic recovery in progress
2009-10-08 12:44:20 CEST LOG:  record with zero length at 0/1051A350
2009-10-08 12:44:20 CEST LOG:  redo is not required
2009-10-08 12:44:20 CEST LOG:  autovacuum launcher started
Note: See TracTickets for help on using tickets.