Traversing Nearest Neighbors With Dijkstra’s Algorithm And SQL Server Graph

James Livingston gives us a Powershell-based implementation of Dijkstra’s shortest path algorithm:

In my previous post I shared a SQL Server 2017 graph database of US capitals. Graphs are a computer science core competency and present some interesting challenges for programmers. Most notable of these challenges is finding the shortest path between nodes. Dijkstra’s algorithm is a commonly taught algorithm for finding shortest path. Dijkstra’s is often asked about during entry level developer interviews and it is a great algorithm to implement when learning a new language since it requires utilizing loops, logic, and data structures.
Here’s my implementation of Dijkstra’s algorithm using PowerShell, traversing a graph of US capitals. Rather than manage our own graph nodes and edges, we’ll utilize graph tables and queries in SQL Server. There’s a lot of different ways to implement this in PowerShell, my first cut of this ended up using a hash table so I could perform random access. There’s a give-and-take with custom PowerShell objects, which sacrifice random access for some other benefits.

Click through for the code.

Related Posts

dbatools 1.0 Available

Chrissy LeMaire and a cast of thousands have officially released dbatools 1.0: We are so super excited to announce that after 5 long years, dbatools 1.0 is publicly available! Our team had some lofty goals and met a vast majority of them . In the end, my personal goal for dbatools 1.0 was to have a […]

Read More

Generating Scripts from SSMS

Jeff Mlakar shows how you can use Management Studio to generate scripts for database objects: Sales.SalesOrderDetail looks like a good choice. Let’s generate a script for that table, all associated objects, and its data. The safest way to create structure including all indexes, keys, defaults, constraints, dependencies, triggers, etc. is to use SSMS Generate Scripts. I […]

Read More

Categories

December 2018
MTWTFSS
« Nov Jan »
 12
3456789
10111213141516
17181920212223
24252627282930
31