root/trunk/sql/sqlserver/shortestPath.sql

IF EXISTS (
  SELECT * FROM dbo.sysobjects WHERE id = OBJECT_ID(N'dbo.shortestPath')
    AND OBJECTPROPERTY(id, N'IsProcedure') = 1)
DROP PROCEDURE shortestPath
GO

CREATE PROCEDURE shortestPath AS
BEGIN
  DECLARE
    @maxLength INT,
    @oldSize INT,
    @newSize INT
  SET @maxLength=1
  SET @oldSize=0
  SET @newSize=1
  
  INSERT INTO paths SELECT head AS startNode,tail AS endNode,1 FROM edges
  
  WHILE @oldSize!=@newSize
  BEGIN
    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)
    
    SET @maxLength=@maxLength+1
    SET @oldSize=@newSize
    SET @newSize=(SELECT COUNT(*) FROM paths)
  END
END
GO

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

EXECUTE shortestPath