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

Powershell Dot-Sourcing

Shane O’Neill takes us through some of the intricacies of dot-sourcing in Powershell: The dot used to represent the location is, as I’ve said before, for the current location. Our ConvertTo-Message02 script changed it’s location as part of the script. When we used the “dot source dot location” method, we weren’t using where our function is as a […]

Read More

Finding Parameter Aliases in Powershell

Mike Robbins has a quick script to find aliases for parameters in Powershell cmdlets: While sitting through Jeff Hicks‘ Advanced PowerShell Scripting Workshop at PowerShell on the River in Chattanooga today, he mentioned there being a “Cn” alias for the ComputerName parameter of commands in PowerShell. I’ve previously written a one-liner to find parameter aliases and at one time Microsoft had starting […]

Read More

Categories

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