frmtest.frm

vb实现最短路径Dijkstra算法

VERSION 5.00
Begin VB.Form frmTest 
   AutoRedraw      =   -1  'True
   Caption         =   "Test"
   ClientHeight    =   5805
   ClientLeft      =   60
   ClientTop       =   345
   ClientWidth     =   8115
   BeginProperty Font 
      Name            =   "Fixedsys"
      Size            =   9
      Charset         =   0
      Weight          =   400
      Underline       =   0   'False
      Italic          =   0   'False
      Strikethrough   =   0   'False
   EndProperty
   LinkTopic       =   "Form2"
   MaxButton       =   0   'False
   ScaleHeight     =   387
   ScaleMode       =   3  'Pixel
   ScaleWidth      =   541
   StartUpPosition =   2  'CenterScreen
   Begin VB.ListBox listGoodPaths 
      BeginProperty Font 
         Name            =   "MS Sans Serif"
         Size            =   8.25
         Charset         =   0
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
      Height          =   1035
      Left            =   5490
      TabIndex        =   4
      Top             =   3090
      Width           =   2535
   End
   Begin VB.TextBox txtFirstChar 
      BeginProperty Font 
         Name            =   "Arial"
         Size            =   9
         Charset         =   177
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
      Height          =   330
      Left            =   6795
      MaxLength       =   1
      TabIndex        =   2
      Text            =   "A"
      Top             =   105
      Width           =   375
   End
   Begin VB.CommandButton cmdDrawAll 
      Caption         =   "Draw All"
      BeginProperty Font 
         Name            =   "MS Sans Serif"
         Size            =   8.25
         Charset         =   0
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
      Height          =   315
      Left            =   6195
      TabIndex        =   1
      Top             =   2205
      Width           =   1170
   End
   Begin VB.ListBox listPaths 
      BeginProperty Font 
         Name            =   "MS Sans Serif"
         Size            =   8.25
         Charset         =   0
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
      Height          =   1035
      Left            =   5460
      TabIndex        =   0
      Top             =   1020
      Width           =   2535
   End
   Begin VB.Label Label3 
      Caption         =   "good paths:"
      BeginProperty Font 
         Name            =   "Arial"
         Size            =   9
         Charset         =   177
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
      Height          =   270
      Left            =   5535
      TabIndex        =   6
      Top             =   2745
      Width           =   1725
   End
   Begin VB.Label Label2 
      Caption         =   "all paths:"
      BeginProperty Font 
         Name            =   "Arial"
         Size            =   9
         Charset         =   177
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
      Height          =   270
      Left            =   5505
      TabIndex        =   5
      Top             =   690
      Width           =   1725
   End
   Begin VB.Label Label1 
      Caption         =   "first label:"
      BeginProperty Font 
         Name            =   "MS Sans Serif"
         Size            =   8.25
         Charset         =   0
         Weight          =   400
         Underline       =   0   'False
         Italic          =   0   'False
         Strikethrough   =   0   'False
      EndProperty
      Height          =   300
      Left            =   5970
      TabIndex        =   3
      Top             =   180
      Width           =   780
   End
End
Attribute VB_Name = "frmTest"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = True
Attribute VB_Exposed = False
'  ==========================================
'  Dijkstra's algorithm to find Shortest Path
'  ==========================================
'
' E.W. Dijkstra is a Dutch professor in Computer
' Science, who did a lot of research in graphs.
'
' Dijkstra's algorithm is of use when working with
' directional graphs. It constructs the shortest path
' between a starting-node and a goal-node.
' It is assumed that every link between two nodes
' has a certain cost, and this algorithm finds the
' path between the two given nodes with the lowest cost.
'
' The idea of this VB project was to show the
' work of this algorithm in a visual way.
'
'    Screen-shot: dijkstra.gif
'
'
'    Visit my Homepage:
'    http://www.geocities.com/emu8086/vb/
'
'
'    Last Update: Saturday, July 20, 2002
'
'
'    Copyright 2002 Alexander Popov Emulation Soft.
'               All rights reserved.
'        http://www.geocities.com/emu8086/


Option Explicit

Private Sub cmdDrawAll_Click()
    Dim i As Integer
    
    Me.Cls
    Me.ForeColor = vbBlack
    
    For i = 0 To listPaths.ListCount - 1
        drawPath (listPaths.List(i))
    Next i

End Sub

Private Sub drawPath(s As String)
    Dim i As Integer
    Dim c As String
    Dim prevX As Integer
    Dim prevY As Integer
    
    i = 1
    CurrentX = 10
    CurrentY = 10
    prevX = -1
    prevY = -1
    
    If txtFirstChar.Text = "" Then txtFirstChar.Text = "A"
    
    Do While (Mid(s, i, 1) <> "")
        c = Mid(s, i, 1)
        CurrentX = (Asc(c) - Asc(txtFirstChar.Text)) * 40 + 10
        If (prevX <> -1) Then
            Line (prevX, prevY + TextHeight("A"))-(CurrentX, CurrentY)
        End If
        prevX = CurrentX
        prevY = CurrentY
        Print c
        i = i + 5
        CurrentY = CurrentY + 40    ' next row
    Loop
End Sub

Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)
'    Caption = X & "   " & Y
End Sub

Private Sub listPaths_Click()
    Dim i As Integer
    
    Me.Cls
    Me.ForeColor = vbBlack
    
    If (listPaths.ListIndex <> -1) Then
        drawPath (listPaths.List(listPaths.ListIndex))
    End If
End Sub

Private Sub listGoodPaths_Click()
    
    cmdDrawAll_Click
    
    If (listGoodPaths.ListIndex <> -1) Then
        Me.ForeColor = vbRed
        drawPath (listGoodPaths.List(listGoodPaths.ListIndex))
    End If
End Sub