root/trunk/sql/mysql/shortestPath.sql

DROP PROCEDURE IF EXISTS shortestPath;

DELIMITER //
CREATE PROCEDURE shortestPath()
BEGIN
  DECLARE maxLength INT DEFAULT 1;
  DECLARE newSize,oldSize INT DEFAULT 0;
  
  INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges;
  
  REPEAT
    INSERT IGNORE INTO paths -- pathsのendNodeから1歩進む
      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;
    
    SET maxLength=maxLength+1;
    SET oldSize=newSize;
    SELECT COUNT(*) INTO newSize FROM paths;
  UNTIL oldSize=newSize -- テーブルpathsが変わらなくなるまで繰り返す
  END REPEAT;
END//
DELIMITER ;

TRUNCATE TABLE paths;

CALL shortestPath();