关于Dijkstra算法的问题
假定无向图为:用于查的两公交站之前最少车站数,查找3到14路不正确,大家看看出了什么问题~详看注释...
程序代码：Option Explicit
Private Sub Command1_Click()
Dim a As Long, b As Long
Dim w() As Long
Dim tNum As Long
Dim i As Long, j As Long
tNum = 15
'初始化权值,与自己的距离为0,若I与J不相邻为-1
ReDim w(tNum - 1, tNum - 1)
For i = 0 To tNum - 1
For j = 0 To tNum - 1
w(i, j) = IIf(i = j, 0, -1)
Next
Next
'下面是手工添加的一些权值,方便测试假设各点间距离为都相同
w(0, 1) = 1
w(0, 2) = 1
w(1, 2) = 1
w(1, 4) = 1
w(1, 0) = 1
w(2, 0) = 1
w(2, 1) = 1
w(2, 4) = 1
w(4, 1) = 1
w(4, 2) = 1
w(4, 3) = 1
w(4, 7) = 1
w(4, 8) = 1
w(4, 11) = 1
w(3, 4) = 1
w(3, 5) = 1
w(5, 3) = 1
w(5, 7) = 1
w(5, 6) = 1
w(5, 12) = 1
w(6, 5) = 1
w(6, 7) = 1
w(6, 9) = 1
w(7, 4) = 1
w(7, 5) = 1
w(7, 6) = 1
w(7, 9) = 1
w(8, 4) = 1
w(8, 9) = 1
w(8, 10) = 1
w(9, 8) = 1
w(9, 7) = 1
w(9, 6) = 1
w(10, 8) = 1
w(11, 4) = 1
w(12, 5) = 1
w(12, 13) = 1
w(13, 12) = 1
w(13, 14) = 1
w(14, 13) = 1
'下面调用显示结果
a = 3
b = 10
Text1.Text = Dijkstra(a, b, tNum, w) '这里的结果是正常的3-->4-->8-->10
'更换起点和终点
a = 3
b = 14
Text2.Text = Dijkstra(a, b, tNum, w) '这里的结果是3-->14,明显不对,正常应该是3-->5-->12-->13-->14
End Sub
'改自网上的一个算法
Function Dijkstra(begin_p As Long, end_p As Long, pointNum As Long, w() As Long) As String
Dim d() As Long
Dim Bj() As Boolean
Dim pre() As Long
Dim i As Long
Dim j As Long
Dim n As Long
n = pointNum - 1
ReDim d(n)
ReDim Bj(n)
ReDim pre(n)
For i = 0 To n
d(i) = -1
Next
For i = 0 To n
Bj(i) = False
Next
For i = 0 To n
d(i) = w(begin_p, i)
pre(i) = begin_p
Next
Dim dis As Long
Dim p_num As Long
Bj(begin_p) = True
For i = 0 To n
dis = -1
p_num = -1
For j = 0 To n
If Not Bj(j) Then
If (dis = -1) Or (d(j) > 0 And dis > d(j)) Then
dis = d(j)
p_num = j
End If
End If
Next
If p_num > 0 Then
Bj(p_num) = True
For j = 0 To n
If w(p_num, j) > 0 And Not Bj(j) Then
If (d(j) = -1) Or (d(j) > -1 And d(p_num) + w(p_num, j) < d(j)) Then
d(j) = d(p_num) + w(p_num, j)
pre(j) = p_num
End If
End If
Next
Else
Exit For
End If
Next
Dim str As String
i = end_p
str = Trim(i)
Do While (i <> begin_p)
i = pre(i)
str = Trim(i) & "-->" & str
Loop
Dijkstra = str
End Function
