Home
Search
 
What's New
Index
Books
Links
Q & A
Newsletter
Banners
 
Feedback
Tip Jar
 
C# Helper...
 
XML RSS Feed
Follow VBHelper on Twitter
 
 
 
MSDN Visual Basic Community
 
 
 
 
 
TitlePerform label setting shortest path calculations in Visual Basic .NET
DescriptionThis example shows how to perform label setting shortest path calculations in Visual Basic .NET.
Keywordsshortest path, shortest path tree, label settings, algorithms, VB .NET
CategoriesAlgorithms, VB.NET
 
This algorithm was adapted from my book Ready-To-Run Visual Basic Algorithms. See that book for more in-depth discussion.

Use the File menu's Open command to load a network from a text file. Click the left mouse button on a node to build the shortest path tree (described shortly) rooted at that node. Then right-click on a node to display the shortest path from the root node to the node you clicked.

The PathSNode class represents a node in the network.

 
Public Class PathSNode
    Public Enum NodeStatusType
        NotInList
        WasInList
        NowInList
    End Enum

    Public Id As Integer
    Public X As Single
    Public Y As Single
    Public Links As New Collection
    Public Dist As Integer              ' Distance from
        ' root of path tree.
    Public NodeStatus As NodeStatusType ' Path tree status.
    Public InLink As PathSLink          ' The link into the
        ' node.
End Class
 
The PathSLink class represents a link between two nodes.
 
Public Class PathSLink
    Public Enum LinkUseageType
        Unused
        InTree
        InPath
    End Enum

    Public Node1 As PathSNode
    Public Node2 As PathSNode
    Public Cost As Integer
    Public LinkUsage As LinkUseageType = _
        LinkUseageType.Unused
End Class
 
Subroutine FindPathTree finds the shortest path tree rooted at a particular node. By following links from a destination node back through the tree, you can trace the shortest path from the root node to the destination node.

The basic idea is this. The routine keeps a candidates collection that holds nodes that are one link away from a node in the current shortest path tree. It keeps track of the best distance so far to every node in the shortest path tree and in the candidates collection.

While the candidates collection is not empty, the program finds the node in the collection with the shortest distance to the root node. Because that node is the closest one to the root, adding other nodes to the shortest path tree cannot improve the path to this node. The program adds that node to the shortest path tree and removes it from the candidate list.

Next the program considers all of the neighbors of the newly added node. If the path to a neighbor via this node is shorter than the path it has currently recorded to the root node, then the program updates the neighbor's path to use the newly added node and then adds it to the candidates collection (if it is not already in the collection).

The program continues this proces, removing a node from the candidates collection, adding it to the shortest path tree, and adding its neighbors to the candidates collection until the collection is empty. At that point the shortest path tree is complete.

 
' Find a shortest path tree rooted at this node
' using a label setting algorithm.
Private Sub FindPathTree(ByVal root As PathSNode)
    Dim candidates As New Collection

    If root Is Nothing Then Exit Sub
    m_Root = root

    ' Reset all nodes' Marked and NodeStatus values,
    ' and all links' Used and LinkUsage flags.
    ResetPathTree()

    ' Start with the root in the shortest path tree.
    root.Dist = 0
    root.InLink = Nothing
    root.NodeStatus = PathSNode.NodeStatusType.NowInList
    candidates.Add(root)

    ' Process the candidates.
    Do While candidates.Count > 0
        ' Find the candidate closest to the root.
        Dim best_dist As Integer = Integer.MaxValue
        Dim best_i As Integer = 0
        For i As Integer = 1 To candidates.Count
            Dim candidate_node As PathSNode = _
                DirectCast(candidates(i), PathSNode)
            Dim new_dist As Integer = candidate_node.Dist
            If new_dist < best_dist Then
                best_i = i
                best_dist = new_dist
            End If
        Next i

        ' Add this node to the shortest path tree.
        Dim node As PathSNode = _
            DirectCast(candidates(best_i), PathSNode)
        candidates.Remove(best_i)
        node.NodeStatus = PathSNode.NodeStatusType.WasInList

        ' Examine the node's neighbors.
        For Each link As PathSLink In node.Links
            Dim to_node As PathSNode
            If node Is link.Node1 Then
                to_node = link.Node2
            Else
                to_node = link.Node1
            End If
            If to_node.NodeStatus = _
                PathSNode.NodeStatusType.NotInList Then
                ' The node has not been in the candidate
                ' list. Add it.
                candidates.Add(to_node)
                to_node.NodeStatus = _
                    PathSNode.NodeStatusType.NowInList
                to_node.Dist = best_dist + link.Cost
                to_node.InLink = link
            ElseIf to_node.NodeStatus = _
                PathSNode.NodeStatusType.NowInList Then
                ' The node is in the candidate list.
                ' Update its Dist and inlink values if
                ' necessary.
                Dim new_dist As Integer = best_dist + _
                    link.Cost
                If new_dist < to_node.Dist Then
                    to_node.Dist = new_dist
                    to_node.InLink = link
                End If
            End If
        Next link
    Loop

    m_GotPathTree = True

    ' Mark the inlinks so they are easy to draw.
    For Each node As PathSNode In m_Nodes
        If Not (node.InLink Is Nothing) Then _
            node.InLink.LinkUsage = _
            PathSLink.LinkUseageType.InTree
    Next node

    ' Start with no destination.
    m_Destination = Nothing

    ' Redraw the network.
    Me.Invalidate()
End Sub
 
See the code for additional details such as how the program loads a network from a text file and how it handles mouse clicks. See my book Ready-To-Run Visual Basic Algorithms for more information on shortest path algorithms and other useful algorithms.
 
 
Copyright © 1997-2006 Rocky Mountain Computer Consulting, Inc.   All rights reserved.
  Updated