Fine dining experience: Chez Dijkstra 

2011 January 28 
Previous Slide  Table of Contents  Next Slide 
SpatiaLite supports an internal routing module called
VirtualNetwork Starting from an arbitrary network this module allows to identify shortest path connections using simple SQL queries. The VirtualNetwork module supports sophisticated and highly optimized algorithms, so it's really fast and very efficient even using huge sized networks. 
Network foundations You cannot assume that any generic road layer corresponds to a network.A real network must satisfy several specific prerequisites, i.e. it has to be a graph. Graph theory is a wide and complex branch of mathematics; if you are interested in this, here you can get some further details: Graph Theory Shortest Path Problem Dijkstra's Algorithm A* Algorithm Very shortly explained:

There are several sources distributing networklike data. One of the most renowned and widely used is OSM [Open Street Map], a completely free worldwide dataset. There are several download sites distributing OSM; just to mention the main ones: Anyway in the following example we'll download the required OSM dataset from: www.gfoss.it Most precisely we'll download the TOSCANA.osm.bz2 dataset. 
>spatialite_osm_net o TOSCANA.osm d tuscany.sqlite T tuscany m SQLite version: 3.7.4 SpatiaLite version: 2.4.0RC5 using INMEMORY database Loading OSM nodes ... wait please ... Loaded 1642867 OSM nodes Verifying OSM ways ... wait please ... Verified 60893 OSM ways Disambiguating OSM nodes ... wait please ... Found 40 duplicate OSM nodes  fixed !!! Loading network ARCs ... wait please ... Loaded 121373 network ARCs Dropping temporary table 'osm_tmp_nodes' ... wait please ... Dropped table 'osm_tmp_nodes' Dropping index 'from_to' ... wait please ... Dropped index 'from_to' exporting IN_MEMORY database ... wait please ... IN_MEMORY database succesfully exported VACUUMing the DB ... wait please ... All done: OSM graph was succesfully loaded > 
SELECT * FROM tuscany; 
id  osm_id  class  node_from  node_to  name  oneway_from_to  oneway_to_from  length  cost  geometry 
...  ...  ...  ...  ...  ...  ...  ...  ...  ...  ... 
2393  8079944  tertiary  659024545  659024546  Via Cavour  1  1  7.468047  0.537699  BLOB sz=80 GEOMETRY 
2394  8079944  tertiary  659024546  156643876  Via Cavour  1  1  12.009911  0.864714  BLOB sz=96 GEOMETRY 
2395  8083989  motorway  31527668  319386487  Autostrada del Sole  1  0  424.174893  13.882087  BLOB sz=80 GEOMETRY 
2396  8083990  motorway  31527665  31527668  Autostrada del Sole  1  0  130.545183  4.272388  BLOB sz=112 GEOMETRY 
...  ...  ...  ...  ...  ...  ...  ...  ...  ...  ... 
SELECT * FROM tuscany_net WHERE NodeFrom = 267209305 AND NodeTo = 267209702; 
Algorithm  ArcRowid  NodeFrom  NodeTo  Cost  Geometry  Name 
Dijkstra  NULL  267209305  267209702  79.253170  BLOB sz=272 GEOMETRY  NULL 
Dijkstra  11815  267209305  250254381  11.170037  NULL  Via Guelfa 
Dijkstra  11816  250254381  250254382  8.583739  NULL  Via Guelfa 
Dijkstra  11817  250254382  250254383  12.465016  NULL  Via Guelfa 
Dijkstra  16344  250254383  256636073  15.638407  NULL  Via Cavour 
Dijkstra  67535  256636073  270862435  3.147105  NULL  Piazza San Marco 
Dijkstra  25104  270862435  271344268  5.175379  NULL  Piazza San Marco 
Dijkstra  25105  271344268  82591712  3.188657  NULL  Piazza San Marco 
Dijkstra  11802  82591712  267209666  4.978328  NULL  Piazza San Marco 
Dijkstra  20773  267209666  267209702  14.906501  NULL  Via Giorgio La Pira 
UPDATE tuscany_net SET Algorithm = 'A*';
UPDATE tuscany_net SET Algorithm = 'Dijkstra'; 
A VirtualNetwork
table simply represents a staticized snapshot of the
underlying network. This allows to adopt an highly efficient binary representation (in other words, allows to produce solutions in a very quick time), but obviously doesn't supports dynamic changes. Each time the underlying network changes the corresponding VirtualNetwork must be DROPped and then created again, so to correctly reflect the latest network state. In many cases this isn't an issue at all: but on some highly dynamic scenario this may be a big annoyance. Be well conscious of this limitation. 
Previous Slide  Table of Contents  Next Slide 
Author: Alessandro Furieri a.furieri@lqt.it  
This work is licensed under the AttributionShareAlike 3.0 Unported (CC BYSA 3.0) license.  
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no FrontCover Texts, and no BackCover Texts. 