Tags

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,


T-SQL Query | [ The Shortest Distance Puzzle ] / [ Graph Shortest Path Puzzle ]

Puzzle Statement

  1. Input table “Area” contains Distance FromPoint , ToPoint and the distance between these points or Areas.
  2. The Puzzle is that you have find out the shortest distance between FromPoint to ToPoint considering all the Paths
  3. Please check out the sample input and expected output for details.

Sample Input

ID FromPoint ToPoint Distance
0 NULL SECTOR 5 0
1 SECTOR 5 SECTOR 22 5
2 SECTOR 5 SECTOR 23 10
3 SECTOR 22 SECTOR 23 15
4 SECTOR 23 SECTOR 14 20
5 SECTOR 22 SECTOR 14 25
6 SECTOR 5 SECTOR 14 35
6 SECTOR 22 SECTOR 31 40
6 SECTOR 23 SECTOR 31 45

Expected Output

Paths Distance
.SECTOR 5..SECTOR 23..SECTOR 14. 30
.SECTOR 5..SECTOR 22..SECTOR 14. 30

Rules/Restrictions

  • Your solution should be should use “SELECT” statement or “CTE
  • Your solution should be generic in nature.
  • Add your solution(s) in the comments section or send you solution(s) to pawankkmr@gmail.com

Script

Use the below script to generate the source table and fill them up with the sample data.


--

CREATE TABLE Area
(      

 ID  INT
,FromPoint VARCHAR(10)
,ToPoint VARCHAR(10)
,Distance INT

)
GO

INSERT INTO Area VALUES
(0 ,NULL       , 'SECTOR 5'  ,0),
(1 ,'SECTOR 5' , 'SECTOR 22' ,05),
(2 ,'SECTOR 5' , 'SECTOR 23' ,10),
(3 ,'SECTOR 22', 'SECTOR 23' ,15),
(4 ,'SECTOR 23', 'SECTOR 14' ,20),
(5 ,'SECTOR 22', 'SECTOR 14' ,25),
(6 ,'SECTOR 5' , 'SECTOR 14' ,35),
(6 ,'SECTOR 22', 'SECTOR 31' ,40),
(6 ,'SECTOR 23', 'SECTOR 31' ,45)

--

Update Apr 29 | Solution 1


--

DECLARE @StartingPoint AS VARCHAR(50) = 'SECTOR 5'
DECLARE @EndingPoint AS VARCHAR(50) = 'SECTOR 14'
;WITH CTE1 AS
(
	SELECT ToPoint ,
		CASE WHEN FromPoint IS NULL THEN CAST('.'+ISNULL(FromPoint,ToPoint)+'.' AS VARCHAR(MAX))
		     WHEN FromPoint IS NOT NULL THEN CAST('.'+FromPoint+'.'+ToPoint+'.' AS VARCHAR(MAX))
		END  FullyQualifiedName
	, Distance FinalDistance
	FROM Area WHERE ( FromPoint = @StartingPoint )
	UNION ALL
	SELECT a.ToPoint , c.FullyQualifiedName+'.'+a.ToPoint+'.' FullyQualifiedName
	, FinalDistance + a.Distance FinalDistance
	FROM Area a INNER JOIN CTE1 c ON a.FromPoint = c.ToPoint
)
,CTE2 AS
(
	SELECT * , RANK() OVER (ORDER BY FinalDistance) rnk FROM CTE1
	WHERE ToPoint = @EndingPoint AND PATINDEX('%'+@EndingPoint+'%',FullyQualifiedName) > 0
)
SELECT FullyQualifiedName, FinalDistance FROM CTE2 WHERE rnk = 1
--

Add a comment if you have any other solution in mind. We all need to learn.

Keep Learning

Http://MSBISkills.com

Advertisements