SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
IF NOT EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[City]') AND type in (N'U'))
BEGIN
CREATE TABLE [dbo].[City](
	[CityID] [int] NOT NULL,
	[Name] [nvarchar](50) NOT NULL,
 CONSTRAINT [PK_City] PRIMARY KEY CLUSTERED 
(
	[CityID] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
END
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
IF NOT EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[Dijkstra]') AND type in (N'P', N'PC'))
BEGIN
EXEC dbo.sp_executesql @statement = N'CREATE PROCEDURE [dbo].[Dijkstra]
	@StartCity Int
AS
BEGIN
	-- Automatically rollback the transaction if something goes wrong.	
	SET XACT_ABORT ON	
	BEGIN TRAN
	
	-- SET NOCOUNT ON added to prevent extra result sets from
	-- interfering with SELECT statements.
	SET NOCOUNT ON;

	-- Create a temporary table for storing the estimates as the algorithm runs
	CREATE TABLE #CityList
	(
		CityId Int NOT NULL,	-- The City Id
		Estimate Int NOT NULL,	-- What is the distance to this city, so far?
		Predecessor Int NULL,	-- The city we came from to get to this city with this distance.
		Done bit NOT NULL		-- Are we done with this city yet (is the estimate the final distance)?
	)

	-- Fill the temporary table with initial data
	INSERT INTO #CityList (CityId, Estimate, Predecessor, Done)
	SELECT CityId, 2147483647, NULL, 0 FROM City
	
	-- Set the estimate for the city we start in to be 0.
	UPDATE #CityList SET Estimate = 0 WHERE CityID = @StartCity
	IF @@rowcount <> 1
	BEGIN
		RAISERROR (''Couldn''''t set start city'', 11, 1) 
		ROLLBACK TRAN		
		RETURN
	END

	DECLARE @FromCity Int, @CurrentEstimate Int

	-- Run the algorithm until we decide that we are finished
	WHILE 1=1
	BEGIN
		-- Reset the variable, so we can detect getting no records in the next step.
		SELECT @FromCity = NULL

		-- Select the CityID and current estimate for a city not done, with the lowest estimate.
		SELECT TOP 1 @FromCity = CityId, @CurrentEstimate = Estimate
		FROM #CityList WHERE Done = 0 AND Estimate < 2147483647
		ORDER BY Estimate
		
		-- Stop if we have no more unvisited, reachable cities.
		IF @FromCity IS NULL BREAK

		-- We are now done with this city.
		UPDATE #CityList SET Done = 1 WHERE CityId = @FromCity

		-- Update the estimates to all neighbour cities of this one (all the cities
		-- there are roads to from this city). Only update the estimate if the new
		-- proposal (to go via the current city) is better (lower).
		UPDATE #CityList SET #CityList.Estimate = @CurrentEstimate + Road.Distance,
			#CityList.Predecessor = @FromCity
		FROM #CityList INNER JOIN Road ON #CityList.CityID = Road.ToCity
		WHERE Road.FromCity = @FromCity AND (@CurrentEstimate + Road.Distance) < #CityList.Estimate
		
	END
	
	-- Select the results.
	SELECT City1.Name AS ToCity, Estimate AS Distance, city2.Name AS Predecessor FROM #CityList
	INNER JOIN City city1 ON #CityList.CityId = City1.CityID
	LEFT OUTER JOIN City city2 ON #CityList.Predecessor = city2.CityID
	
	-- Drop the temp table.
	DROP TABLE #CityList
	
	COMMIT TRAN
END
' 
END
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
IF NOT EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[Road]') AND type in (N'U'))
BEGIN
CREATE TABLE [dbo].[Road](
	[FromCity] [int] NOT NULL,
	[ToCity] [int] NOT NULL,
	[Distance] [int] NOT NULL,
 CONSTRAINT [PK_Road] PRIMARY KEY CLUSTERED 
(
	[FromCity] ASC,
	[ToCity] ASC,
	[Distance] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]
END
GO
IF NOT EXISTS (SELECT * FROM sys.foreign_keys WHERE object_id = OBJECT_ID(N'[dbo].[FK_Road_City_From]') AND parent_object_id = OBJECT_ID(N'[dbo].[Road]'))
ALTER TABLE [dbo].[Road]  WITH CHECK ADD  CONSTRAINT [FK_Road_City_From] FOREIGN KEY([FromCity])
REFERENCES [dbo].[City] ([CityID])
GO
ALTER TABLE [dbo].[Road] CHECK CONSTRAINT [FK_Road_City_From]
GO
IF NOT EXISTS (SELECT * FROM sys.foreign_keys WHERE object_id = OBJECT_ID(N'[dbo].[FK_Road_City_To]') AND parent_object_id = OBJECT_ID(N'[dbo].[Road]'))
ALTER TABLE [dbo].[Road]  WITH CHECK ADD  CONSTRAINT [FK_Road_City_To] FOREIGN KEY([ToCity])
REFERENCES [dbo].[City] ([CityID])
GO
ALTER TABLE [dbo].[Road] CHECK CONSTRAINT [FK_Road_City_To]
GO