SQLite Forum

SQLite3 Array?
Login
I think we have done this before:

```
create table edges
(
    fromNode    integer not null,
    toNode      integer not null,
    distance    numeric not null default 1,
    isOneWay    integer not null check(isOneWay in (True, False)) default True,
    primary key (fromNode, toNode)
) without rowid;

create unique index backedges on edges (toNode, fromNode, distance) where not isOneWay;

insert into edges(fromNode, toNode, isOneWay, distance) values
    (1, 2, True, 100),
    (1, 3, True,  70),
    (2, 3, False, 20),
    (3, 4, True,  40),
    (2, 5, True,  30),
    (4, 5, True,  20),
    (5, 6, True,  20),
    (4, 6, True,  80);

.parameter init
.parameter set :start 1
.parameter set :end 6
.parameter set :maxhops 10

with paths (startAt, endAt, visited, hops, pathDistance)
  as (
         select :start                      as startAt,
                :start                      as endAt,
                '/' || :start || '/'        as visited,
                0                           as hops,
                0                           as pathDistance
      union all
         select startAt                     as startAt,
                toNode                      as endAt,
                visited || toNode || '/'    as visited,
                hops + 1                    as hops,
                pathDistance + distance     as pathDistance
           from paths, edges
          where fromNode == endAt
            and instr(visited, '/' || toNode || '/') == 0
            and instr(visited, '/' || :end || '/') == 0
            and hops < :maxhops
      union all
         select startAt                     as startAt,
                fromNode                    as endAt,
                visited || fromNode || '/'  as visited,
                hops + 1                    as hops,
                pathDistance + distance     as pathDistance
           from paths, edges
          where toNode == endAt
            and not isOneWay
            and instr(visited, '/' || fromNode || '/') == 0
            and instr(visited, '/' || :end || '/') == 0
            and hops < :maxhops
       order by 5
    )
  select *
    from paths
   where startAt == :start
     and endAt == :end
order by pathDistance, hops
;
┌─────────┬───────┬───────────────┬──────┬──────────────┐
│ startAt │ endAt │    visited    │ hops │ pathDistance │
├─────────┼───────┼───────────────┼──────┼──────────────┤
│ 1       │ 6     │ /1/3/2/5/6/   │ 4    │ 140          │
│ 1       │ 6     │ /1/2/5/6/     │ 3    │ 150          │
│ 1       │ 6     │ /1/3/4/5/6/   │ 4    │ 150          │
│ 1       │ 6     │ /1/3/4/6/     │ 3    │ 190          │
│ 1       │ 6     │ /1/2/3/4/5/6/ │ 5    │ 200          │
│ 1       │ 6     │ /1/2/3/4/6/   │ 4    │ 240          │
└─────────┴───────┴───────────────┴──────┴──────────────┘
```

You could also add "cost" to each edge (eg, minutes to drive) to get an enumeration of the "cost" of each path since the minimum distance might give a different answer that the minimum cost.