PostgreSQL - Shortest Path

Question

I have a Grid Table, that stores a Start-point and a Destination-point. It looks like this:

  src  | dest  | cost 
-------+-------+------
 {1,1} | {1,2} |    1
 {1,1} | {2,1} |    1
 {1,2} | {1,1} |    1
 {1,2} | {1,3} |    1
 {1,2} | {2,2} |    1
 ...
 {4,5} | {5,5} |    1

I want to start from my start-point, then step to one of its neighbours, then to his neighbours and so on.

I have this code so far (the counter is just to make sure that i dont get stuck in an endless loop):

WITH RECURSIVE

init (here, there, cost_to_here, counter, path ) AS (
SELECT g.src, g.dest, 0.0, 1, array[g.src, g.dest]  -- SourcePoint with a cost of 0 src -> src
FROM grid AS g
WHERE g.src = '{1,1}'

UNION ALL

(WITH init(here, there, cost_to_here, counter, path) AS (TABLE init)  -- Reference the working Table once

SELECT g.src, g.dest, i1.cost_to_here + g.cost, i1.counter + 1, i1.path || array[g.dest]
FROM grid AS g, init AS i1
WHERE g.src = i1.there
AND NOT g.dest = ANY(i1.path)
AND (i1.here) IN (select i2.here
                   from init as i2)
and i1.counter < 7


 )
)
table init;

I start from my src point, which is {1,1} and visit its neighbours. Since i don't want to go back to a point i already visited,i check if i already visited my next point.

This is what the code does:

 here  | there | cost_to_here | counter |                               path                                
-------+-------+--------------+---------+--------------------------------------
 {1,1} | {1,2} |          0.0 |       1 | {"{1,1}","{1,2}"}
 {1,1} | {2,1} |          0.0 |       1 | {"{1,1}","{2,1}"}
 {1,2} | {1,3} |          1.0 |       2 | {"{1,1}","{1,2}","{1,3}"}
 {1,2} | {2,2} |          1.0 |       2 | {"{1,1}","{1,2}","{2,2}"}
 {2,1} | {2,2} |          1.0 |       2 | {"{1,1}","{2,1}","{2,2}"}
 ...
 {1,2} | {1,3} |          3.0 |       4 | {"{1,1}","{2,1}","{2,2}","{1,2}","{1,3}"}
 {2,3} | {1,3} |          3.0 |       4 | {"{1,1}","{1,2}","{2,2}","{2,3}","{1,3}"}

As you can see it generates me different paths to {1,3}. How can i manage to just keep the best one ?

But i only want to keep the best path. How do i manage that ?

does PostgreSQL support CONNECT BY yet? if so there are several functions to help. — Randy, Nov 19 '17 at 14:34
@Randy: Nope. See: https://stackoverflow.com/a/22627228/939860 — Erwin Brandstetter, Nov 19 '17 at 15:09

score 1 · Accepted Answer · answered Nov 19 '17 at 14:32

1

Afterwards, just keep the shortest one. Something like this:

select distinct on (src, dest) i.*
from init 8
order by src, dest, cost_to_here;

answered Nov 19 '17 at 14:32

Gordon Linoff

1,242,037
58
646
786

PostgreSQL - Shortest Path

1 Answers1