PostgreSQL - 最短経路

Question

私はスタートポイントとデスティネーションポイントを格納するグリッドテーブルを持っています。

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 

私がそうで、その後の彼の隣人に、隣国の一つにステップしてから、私の始点から開始したい： それはこのようになります。

私はこのコードを持って、これまで（カウンターはちょうど私が無限ループにはまりいけないことを確認することです）：

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; 

私は{1,1}をである私のsrc点から開始し、隣国を訪問。すでに訪問したポイントに戻って欲しくないので、私はすでに次のポイントに行ったかどうかを確認します。

これは、コードが何をするかです：

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}"} 

あなたはそれが{1,3}に私の異なるパスを生成し、見ることができるように。どのようにして最高のものを保つことができますか？

しかし、私は最良の経路を維持したいだけです。 どうすればそれを管理できますか？

Answer 1

その後、最短のままにしてください。このようなもの：

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