root/trunk/sql/postgresql/shortestPath.sql

DROP FUNCTION shortestPath();

CREATE FUNCTION shortestPath() RETURNS void AS '
DECLARE
  maxLength INT:=1;
  oldSize INT;
  newSize INT:=0;
BEGIN
  INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges;
  
  LOOP
    INSERT INTO paths
      SELECT DISTINCT p.startNode AS startNode,tail AS endNode,maxLength+1 AS length
      FROM paths p
      JOIN edges ON p.endNode=head
      WHERE p.length=maxLength
        AND p.startNode!=tail
        AND NOT EXISTS (
          SELECT * FROM paths q
          WHERE q.startNode=p.startNode AND q.endNode=tail);
    maxLength:=maxLength+1;
    oldSize:=newSize;
    SELECT COUNT(*) INTO newSize FROM paths;
    IF oldSize=newSize THEN
      EXIT;
    END IF;
  END LOOP;
END;
' LANGUAGE plpgsql;

TRUNCATE TABLE paths; -- こうした方が速い

SELECT shortestPath();