-- delete previous map
exec dbo.uspdijkstrainitializemap

-- create a new map
exec dbo.uspdijkstraaddpath 'a', 'b',  4
exec dbo.uspdijkstraaddpath 'a', 'd',  1
exec dbo.uspdijkstraaddpath 'b', 'a', 74
exec dbo.uspdijkstraaddpath 'b', 'c',  2
exec dbo.uspdijkstraaddpath 'b', 'e', 12
exec dbo.uspdijkstraaddpath 'c', 'b', 12
exec dbo.uspdijkstraaddpath 'c', 'f', 74
exec dbo.uspdijkstraaddpath 'c', 'j', 12
exec dbo.uspdijkstraaddpath 'd', 'e', 32
exec dbo.uspdijkstraaddpath 'd', 'g', 22
exec dbo.uspdijkstraaddpath 'e', 'd', 66
exec dbo.uspdijkstraaddpath 'e', 'f', 76
exec dbo.uspdijkstraaddpath 'e', 'h', 33
exec dbo.uspdijkstraaddpath 'f', 'i', 11
exec dbo.uspdijkstraaddpath 'f', 'j', 21
exec dbo.uspdijkstraaddpath 'g', 'd', 12
exec dbo.uspdijkstraaddpath 'g', 'h', 10
exec dbo.uspdijkstraaddpath 'h', 'g',  2
exec dbo.uspdijkstraaddpath 'h', 'i', 72
exec dbo.uspdijkstraaddpath 'i', 'f', 31
exec dbo.uspdijkstraaddpath 'i', 'j',  7
exec dbo.uspdijkstraaddpath 'i', 'h', 18
exec dbo.uspdijkstraaddpath 'j', 'f',  8

-- resolve route
exec dbo.uspdijkstraresolve 'a', 'i'

From	To	Cost
----	--	----
a	b	 4
b	c	 6
c	j	18
j	f	26
f	i	37

CREATE TABLE [dbo].[Nodes] (
	[NodeID] [int] IDENTITY (1, 1) NOT NULL ,
	[NodeName] [varchar] (20) COLLATE Finnish_Swedish_CI_AS NOT NULL ,
	[Cost] [int] NULL ,
	[PathID] [int] NULL ,
	[Calculated] [tinyint] NOT NULL 
) ON [PRIMARY]
GO

CREATE TABLE [dbo].[Paths] (
	[PathID] [int] IDENTITY (1, 1) NOT NULL ,
	[FromNodeID] [int] NOT NULL ,
	[ToNodeID] [int] NOT NULL ,
	[Cost] [int] NOT NULL 
) ON [PRIMARY]
GO

ALTER TABLE [dbo].[Nodes] WITH NOCHECK ADD 
	CONSTRAINT [PK_Nodes] PRIMARY KEY  CLUSTERED 
	(
		[NodeID]
	)  ON [PRIMARY] 
GO

ALTER TABLE [dbo].[Paths] WITH NOCHECK ADD 
	CONSTRAINT [PK_Paths] PRIMARY KEY  CLUSTERED 
	(
		[PathID]
	)  ON [PRIMARY] 
GO

ALTER TABLE [dbo].[Paths] ADD 
	CONSTRAINT [FK_Paths_FromNodes] FOREIGN KEY 
	(
		[FromNodeID]
	) REFERENCES [dbo].[Nodes] (
		[NodeID]
	),
	CONSTRAINT [FK_Paths_ToNodes] FOREIGN KEY 
	(
		[ToNodeID]
	) REFERENCES [dbo].[Nodes] (
		[NodeID]
	)
GO

CREATE PROCEDURE dbo.uspDijkstraInitializeMap
AS

DELETE
FROM	Paths

DBCC CHECKIDENT (Paths, RESEED, 0)

DELETE
FROM	Nodes

DBCC CHECKIDENT (Nodes, RESEED, 0)
GO

CREATE PROCEDURE dbo.uspDijkstraClearMap
AS

UPDATE	Nodes
SET	PathID = NULL,
	Cost = NULL,
	Calculated = 0
GO

CREATE PROCEDURE dbo.uspDijkstraAddPath
(
	@FromNodeName VARCHAR(20),
	@ToNodeName VARCHAR(20),
	@Cost INT
)
AS

SET NOCOUNT ON

DECLARE	@FromNodeID INT,
	@ToNodeID INT,
	@PathID INT

SELECT	@FromNodeID = NodeID
FROM	Nodes
WHERE	NodeName = @FromNodeName

IF @FromNodeID IS NULL
	BEGIN
		INSERT	Nodes
			(
				NodeName,
				Calculated
			)
		VALUES	(
				@FromNodeName,
				0
			)

		SELECT	@FromNodeID = SCOPE_IDENTITY()
	END

SELECT	@ToNodeID = NodeID
FROM	Nodes
WHERE	NodeName = @ToNodeName

IF @ToNodeID IS NULL
	BEGIN
		INSERT	Nodes
			(
				NodeName,
				Calculated
			)
		VALUES	(
				@ToNodeName,
				0
			)

		SELECT	@ToNodeID = SCOPE_IDENTITY()
	END

SELECT	@PathID = PathID
FROM	Paths
WHERE	FromNodeID = @FromNodeID
	AND ToNodeID = @ToNodeID

IF @PathID IS NULL
	INSERT	Paths
		(
			FromNodeID,
			ToNodeID,
			Cost
		)
	VALUES	(
			@FromNodeID,
			@ToNodeID,
			@Cost
		)
ELSE
	UPDATE	Paths
	SET	Cost = @Cost
	WHERE	FromNodeID = @FromNodeID
		AND ToNodeID = @ToNodeID
GO

CREATE PROCEDURE dbo.uspDijkstraResolve
(
	@FromNodeName VARCHAR(20),
	@ToNodeName VARCHAR(20)
)
AS

SET NOCOUNT ON

EXEC dbo.uspDijkstraClearMap

DECLARE	@FromNodeID INT,
	@ToNodeID INT,
	@NodeID INT,
	@Cost INT,
	@PathID INT

SELECT	@FromNodeID = NodeID,
	@NodeID = NodeID
FROM	Nodes
WHERE	NodeName = @FromNodeName

IF @FromNodeID IS NULL
	BEGIN
		SELECT	@FromNodeName = ISNULL(@FromNodeName, '')
		RAISERROR ('From node name ''%s'' can not be found.', 16, 1, @FromNodeName) 
		RETURN
	END

SELECT	@ToNodeID = NodeID
FROM	Nodes
WHERE	NodeName = @ToNodeName

IF @ToNodeID IS NULL
	BEGIN
		SELECT	@ToNodeName = ISNULL(@ToNodeName, '')
		RAISERROR ('To node name ''%s'' can not be found.', 16, 1, @ToNodeName) 
		RETURN
	END

UPDATE	Nodes
SET	Cost = 0
WHERE	NodeID = @FromNodeID

WHILE @NodeID IS NOT NULL
	BEGIN
		UPDATE		ToNodes
		SET		ToNodes.Cost =	CASE
							WHEN ToNodes.Cost IS NULL THEN FromNodes.Cost + Paths.Cost
							WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost THEN FromNodes.Cost + Paths.Cost
							ELSE ToNodes.Cost
						END,
				ToNodes.PathID = Paths.PathID
		FROM		Nodes AS FromNodes
		INNER JOIN	Paths ON Paths.FromNodeID = FromNodes.NodeID
		INNER JOIN	Nodes AS ToNodes ON ToNodes.NodeID = Paths.ToNodeID
		WHERE		FromNodes.NodeID = @NodeID
				AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
				AND ToNodes.Calculated = 0

		UPDATE	FromNodes
		SET	FromNodes.Calculated = 1
		FROM	Nodes AS FromNodes
		WHERE	FromNodes.NodeID = @NodeID

		SELECT	@NodeID = NULL

		SELECT TOP 1	@NodeID = Nodes.NodeID
		FROM		Nodes
		WHERE		Nodes.Calculated = 0
				AND Nodes.Cost IS NOT NULL
		ORDER BY	Nodes.Cost
	END

CREATE TABLE	#Map
		(
			RowID INT IDENTITY(-1, -1),
			FromNodeName VARCHAR(20),
			ToNodeName VARCHAR(20),
			Cost INT
		)

IF EXISTS (SELECT NULL FROM Nodes WHERE NodeID = @ToNodeID AND Cost IS NULL)
	BEGIN
		SELECT	FromNodeName,
			ToNodeName,
			Cost
		FROM	#Map

		DROP TABLE #Map

		RETURN
	END

WHILE @FromNodeID <> @ToNodeID
	BEGIN
		SELECT		@FromNodeName = FromNodes.NodeName,
				@ToNodeName = ToNodes.NodeName,
				@Cost = ToNodes.Cost,
				@PathID = ToNodes.PathID
		FROM		Nodes AS ToNodes
		INNER JOIN	Paths ON Paths.PathID = ToNodes.PathID
		INNER JOIN	Nodes AS FromNodes ON FromNodes.NodeID = Paths.FromNodeID
		WHERE		ToNodes.NodeID = @ToNodeID

		INSERT	#Map
			(
				FromNodeName,
				ToNodeName,
				Cost
			)
		VALUES	(
				@FromNodeName,
				@ToNodeName,
				@Cost
			)

		SELECT	@ToNodeID = Paths.FromNodeID
		FROM	Paths
		WHERE	Paths.PathID = @PathID
	END

SELECT		FromNodeName,
		ToNodeName,
		Cost
FROM		#Map
ORDER BY	RowID

DROP TABLE #Map
GO

quote:

---

Originally posted by Peso

You mean like Fourier transformations?


Peter Larsson
Helsingborg, Sweden

---

    A
    |
B - C - D