Dijkstra   1 comment

 

I recently received the following question:

Im  trying to solve the following problem in Powershell:

 I know the name of Active Directory Site A and the name of Active Directory Site B, Site A doesn’t necessarily have a site link to Site B (could go A -> C -> B). What is the total cost of the least cost path between these 2 sites? What is the total cost between any 2 sites? (effectively I’m trying to replace this : http://msdn.microsoft.com/library/default.asp?url=/library/en-us/ad/ad/dsquerysitesbycost.asp api with a Powershell version.)

To do so, I think I need to implement some kind of Dijkstra engine  to solve this…

 Yay for Wikipedia (http://en.wikipedia.org/wiki/Dijkstra)!

 Bruce and I thought it might be fun to put this together – we took it straight from the C code.  Given the following graph

Where the weight of the path is written on the line.  Here’s the output from running the script:

PS> get-dijkstra
The distance between nodes 0 and 0 is 0
The distance between nodes 0 and 1 is 2
The distance between nodes 0 and 2 is 1
The distance between nodes 0 and 3 is 5
The distance between nodes 0 and 4 is 4
The distance between nodes 0 and 5 is 6
The distance between nodes 0 and 6 is 6
The distance between nodes 0 and 7 is 8

Showing that the shortest path is 8!  Unfortunately, this script doesn’t show the nodes in the path.  I’ll leave that as an exercise for the reader.  The real point of the exercise was to show the amount of effort that was needed to convert the C into PowerShell!  We basically had to create the structures in the C code, which we did via HashTables (and used functions to create the hashtables).

Here’s the script (again, a straight forward port of the C code from the Wiki site, it’s basic but it works!):

### get-dijkstra.ps1
$INFINITY = [int]::MaxValue-1
function edge ([int] $weight, [int] $dest)
{
    @{weight = $weight; dest = $dest}
}

function Vertex( [object[]] $connections)
{
    @{
       connections = $connections; # An array of weighted arcs
       numconnect = $connections.length
       distance = $INFINITY
       isDead = $false
    }
}

function Dijkstra([object[]] $graph, [int] $source)
{
    [int] $nodecount = $graph.length
    $graph[$source].distance = 0
    for($i = 0; $i -lt $nodecount; $i++) {
        $min = $INFINITY+1
        # find the unchecked node closest to the source
        for($j = 0; $j -lt $nodecount; $j++) {
            if(! $graph[$j].isDead -and $graph[$j].distance -lt $min) {
                $next = $j
                $min = $graph[$j].distance
            }
        }
        # check all paths from node 
        for($j = 0; $j -lt $graph[$next].numconnect; $j++)
        {
            if($graph[$graph[$next].connections[$j].dest].distance -gt
               $graph[$next].distance + $graph[$next].connections[$j].weight)
            {
                $graph[$graph[$next].connections[$j].dest].distance =
                    $graph[$next].distance + $graph[$next].connections[$j].weight
            }
        }
        $graph[$next].isDead = $true
    }
    for([int] $i = 0; $i -lt $nodecount; $i++) {
        "The distance between nodes {0} and {1} is {2}" -f
            $source, $i, $graph[$i].distance
    }
}
$graph = @()
###
### Here’s where we define the different vertexi
### each vertex is a collection of edges
### an edge has a weight and a destination
$graph += vertex (edge -w 1 -d 2),(edge -w 2 -d 1) # 0
$graph += vertex (edge -w 3 -d 3),(edge -w 4 -d 4) # 1
$graph += vertex (edge -w 3 -d 4),(edge -w 5 -d 6),(edge -w 10 -d 7) # 2
$graph += vertex (edge -w 3 -d 5) # 3
$graph += vertex (edge -w 2 -d 5),(edge -w 3 -d 6) # 4
$graph += vertex (edge -w 2 -d 6),(edge -w 2 -d 7) # 5
$graph += vertex (edge -w 2 -d 7) # 6
$graph += vertex (edge -w 0 -d 0) # 7
Dijkstra $graph 0

### END SCRIPT

 Woo Hoo!

 

 

 

Advertisements

Posted October 16, 2006 by jtruher3 in PowerShell

One response to “Dijkstra

Subscribe to comments with RSS.

  1. That\’s a really useful example to people out there.  I feel like the community of administrators in the windows world aren\’t getting excited about powershell, but maybe I\’m completely off base.  That is a really a shame though, since from everything I\’ve seen its more useful than finding a bag in an rpg.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: