Dijkstra’s Algorithm in PowerShell and SQL Server Graph

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.

# Replace these values with your instance and database
$SQLInstance    = 'sql2017'
$GraphDB        = 'graph'

# The city we wish to find the shortest paths from
$CurrentCity    = 'Salem'

Next, I’ll create a hash table, query SQL Server for nodes, and populate the hash table.

# Initialize and populate our graph data structure.
$Cities = @{}

$AllCities = Invoke-SQLCMD -ServerInstance $SQLInstance -Database $GraphDB -Query 'SELECT name FROM capitals'

# Give each city a high mileage and mark them un-visited.
foreach ($City in $AllCities) {
    $Record = "" | Select-Object miles, visited
    $Record.miles       = [int]10000
    $Record.visited     = $false

    $Cities.Add($City.name, $Record)
}

Next, mark your current city as having 0 miles, and store the number of un-visited cities, and start a loop to process all un-visited cities.

$Cities[$CurrentCity].miles = 0

$UnvisitedCities = ($Cities.GetEnumerator() | Where-Object {$_.Value.visited -eq $false} | Measure-Object).Count

while ($UnvisitedCities -gt 0) {

Query SQL Server for edge information from your current city. This query will return all neighboring capitals and their distances. If you’re not familiar with the MATCH component or querying graphs, see Robert Sheldon’s post.

    $NeighborsQuery   = "SELECT cityTo.name AS toName, distances.miles
                        FROM capitals AS cityFrom, distances, capitals AS cityTo
                        WHERE MATCH (cityFrom-(distances)->cityTo)
                        AND cityFrom.name = '$CurrentCity'"
    $Neighbors = Invoke-SQLCMD -ServerInstance $SQLInstance -Database $GraphDB -Query $NeighborsQuery

Now, for each neighbor, determine if you have found a shorter route through the current node. If you have, update the distance.

    foreach ($Neighbor in $Neighbors) {

        # If the neighbor has been visited, don't process it
        if ($Cities[$Neighbor.toName].visited -ne $true) {
            # Update the distance to the neighbor through the current city
            $CurrentMileage = $Cities[$CurrentCity].miles + $Neighbor.miles

            # If the current path is shorter than the neighbors current shortest path, update it
            if ($CurrentMileage -lt $Cities[$Neighbor.toName].miles) {
                $Cities[$Neighbor.toName].miles = $CurrentMileage
            }
        }
    }

Once we’ve processed all neighboring nodes, we can mark the node as visited.

    # Mark the city visited
    $Cities[$CurrentCity].visited = $true

Because I’m using a hash table, we need to loop to find the next city that we want to visit. Dijkstra’s dictates we visit the un-visited city with the shortest distance.

    # Find the next un-visited city to visit.
    $Shortest = 100000
    foreach ($City in $Cities.GetEnumerator() | Where-Object {$_.Value.visited -eq $false}) {
        if ($City.Value.miles -lt $Shortest) {
            $Shortest       = $City.Value.miles
            $CurrentCity    = $City.Name 
        }
    }

Once we’ve found it, update the un-visited cities count and close the loop.

<br />    # Update the un-visited cities count
    $UnvisitedCities = ($Cities.GetEnumerator() | Where-Object {$_.Value.visited -eq $false} | Measure-Object).Count
}

Finally, spit out the results by returning the hash table. The hash table will now have updated distances which reflect the shortest distance from your starting city.

# Return the results
$Cities

Here’s the entire script:

# Replace these values with your instance and database
$SQLInstance    = 'sql2017'
$GraphDB        = 'graph'

# The city we wish to find the shortest paths from
$CurrentCity    = 'Salem'

# Initialize and populate our graph data structure.
$Cities = @{}

$AllCities = Invoke-SQLCMD -ServerInstance $SQLInstance -Database $GraphDB -Query 'SELECT name FROM capitals'

foreach ($City in $AllCities) {
    $Record = "" | Select-Object miles, visited
    $Record.miles       = [int]10000
    $Record.visited    = $false

    $Cities.Add($City.name, $Record)
}

$Cities[$CurrentCity].miles = 0

$UnvisitedCities = ($Cities.GetEnumerator() | Where-Object {$_.Value.visited -eq $false} | Measure-Object).Count

while ($UnvisitedCities -gt 0) {

    $NeighborsQuery   = "SELECT cityTo.name AS toName, distances.miles
                        FROM capitals AS cityFrom, distances, capitals AS cityTo
                        WHERE MATCH (cityFrom-(distances)->cityTo)
                        AND cityFrom.name = '$CurrentCity'"
    $Neighbors = Invoke-SQLCMD -ServerInstance $SQLInstance -Database $GraphDB -Query $NeighborsQuery

    foreach ($Neighbor in $Neighbors) {

        #if the neighbor has been visited, don't process it
        if ($Cities[$Neighbor.toName].visited -ne $true) {
            # Update the distance to the neighbor through the current city
            $CurrentMileage = $Cities[$CurrentCity].miles + $Neighbor.miles

            # If the current path is shorter than the neighbors current shortest path, update it
            if ($CurrentMileage -lt $Cities[$Neighbor.toName].miles) {
                $Cities[$Neighbor.toName].miles = $CurrentMileage
            }
        }
    }

    # Mark the city visited
    $Cities[$CurrentCity].visited = $true

    # Find the next un-visited city to visit.
    $Shortest = 100000
    foreach ($City in $Cities.GetEnumerator() | Where-Object {$_.Value.visited -eq $false}) {
        if ($City.Value.miles -lt $Shortest) {
            $Shortest       = $City.Value.miles
            $CurrentCity    = $City.Name 
        }
    }

    # Update the unvisited cities count
    $UnvisitedCities = ($Cities.GetEnumerator() | Where-Object {$_.Value.visited -eq $false} | Measure-Object).Count
}

# Return the results
$Cities

Whew.

-Cheers

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.