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!
Tools 
