RT.
ab(0) = "牧野草原00,牧野草原01,牧野草原05,牧野草原07"
ab(1) = "牧野草原01,牧野草原00,牧野草原02"
ab(2) = "牧野草原02,牧野草原01,牧野草原12,牧野草原13"
ab(3) = "牧野草原03,牧野草原14,村口"
ab(4) = "牧野草原04,牧野草原06,牧野草原08,牧野草原10"
ab(5) = "牧野草原05,牧野草原00,牧野草原06"
ab(6) = "牧野草原06,牧野草原04,牧野草原05,万马草原_03"
ab(7) = "牧野草原07,牧野草原00,牧野草原10"
ab(8) = "牧野草原08,牧野草原04,牧野草原15,牧野草原16"
ab(9) = "牧野草原09,牧野草原22,牧野草原23"
ab(10) = "牧野草原10,牧野草原04,牧野草原07,牧野草原11"
ab(11) = "牧野草原11,牧野草原10,牧野草原12"
ab(12) = "牧野草原12,牧野草原11,牧野草原13"
ab(13) = "牧野草原13,牧野草原12,牧野草原14,牧野草原02"
ab(14) = "牧野草原14,牧野草原03,牧野草原13,牧野草原18"
ab(15) = "牧野草原15,牧野草原18,牧野草原20"
ab(16) = "牧野草原16,牧野草原18,牧野草原20"
ab(17) = "牧野草原17,牧野草原12,牧野草原24"
ab(18) = "牧野草原18,牧野草原14,牧野草原24"
ab(19) = "牧野草原20,牧野草原15,牧野草原16,牧野草原26"
ab(20) = "牧野草原21,牧野草原22,牧野草原26"
ab(21) = "牧野草原22,牧野草原21,牧野草原32"
ab(22) = "牧野草原23,牧野草原09,牧野草原24,牧野草原33"
ab(23) = "牧野草原24,牧野草原17,牧野草原18,牧野草原23"
ab(24) = "牧野草原26,牧野草原20,牧野草原21,牧野草原30"
ab(25) = "牧野草原27,牧野草原25,牧野草原34"
ab(26) = "牧野草原28,牧野草原25,牧野草原34,牧野草原35"
ab(27) = "牧野草原30,牧野草原26,牧野草原31"
ab(28) = "牧野草原31,牧野草原30,牧野草原32"
ab(29) = "牧野草原32,牧野草原22,牧野草原31,牧野草原33"
ab(30) = "牧野草原33,牧野草原23,牧野草原32,牧野草原36"
ab(31) = "牧野草原34,牧野草原27,牧野草原28,牧野草原36"
ab(32) = "牧野草原35,牧野草原28,低矮林地"
ab(33) = "牧野草原36,牧野草原33,牧野草原34"
ab(34) = "万马草原_03,牧野草原06"
ab(35) = "低矮林地,牧野草原28"
上面是一个游戏中的地图的数据。地图一共有36个点,放在ab数组中,
split(ab(i),",")(0)是它的父结点,split(ab(i),",")(1-结束) 是它可以走到的临点, 问题是,我在这个图的任一点(StartWay)到结束的任何一点(EndWay),最近的一种走法,每次只能走一个点
问题补充:帮帮啦。OK再送50分 比如我现在的位置在 牧野草原04 即位置在ab(04)中
ab(4)(0)是点的位置,即 牧野草原04 它的临点,牧野草原06,牧野草原08,牧野草原10
也就是说。我在04可以走到06,08,10
这个函数可以取出,现在的位置所在,数组的第几位 Function ArrId(tem) As Integer
ArrId = -1
For ArrId_i = 0 To UBound(ab)
If Split(ab(ArrId_i), ",")(0) = tem Then
ArrId = ArrId_i
Exit For
End If
Next
End Function
个人对广度优先算法的理解是每次优先遍历父结点下的直接子结点,遍历完这些直接子结点之后再从这些子结点开始遍历他们的直接子结点,以此类推下去,直到找到终点。所以,此处肯定是需要使用到迭代了。在此我想写出我的思路来与楼主交流下。
1.确定startway点和endway点以后,找到startway点,并对该点下的子结点进行遍历。如你此处选择的startway是牧野草原04 即位置在ab(04),endway是牧野草原15,那么ab(04)下的直接子结点可认为是牧野草原06、牧野草原08和牧野草原10。我们开始按照广度优先算法遍历到牧野草原15。
2.首先我们遍历完04的子结点(06,08,10),发现没有15。
3.接下来我们遍历结点06的子结点(04,05,03),发现没有15.
4.然后,我们开始遍历结点08的子结点(4,15,16),发现15,于是整个遍历结束。
PS:对于回路的子结点不应该考虑遍历,比如06中04的回路。
麻烦各位。给写一下。
ab(0) = "牧野草原00,牧野草原01,牧野草原05,牧野草原07"
ab(1) = "牧野草原01,牧野草原00,牧野草原02"
ab(2) = "牧野草原02,牧野草原01,牧野草原12,牧野草原13"
ab(3) = "牧野草原03,牧野草原14,村口"
ab(4) = "牧野草原04,牧野草原06,牧野草原08,牧野草原10"
ab(5) = "牧野草原05,牧野草原00,牧野草原06"
ab(6) = "牧野草原06,牧野草原04,牧野草原05,万马草原_03"
ab(7) = "牧野草原07,牧野草原00,牧野草原10"
ab(8) = "牧野草原08,牧野草原04,牧野草原15,牧野草原16"
ab(9) = "牧野草原09,牧野草原22,牧野草原23"
ab(10) = "牧野草原10,牧野草原04,牧野草原07,牧野草原11"
ab(11) = "牧野草原11,牧野草原10,牧野草原12"
ab(12) = "牧野草原12,牧野草原11,牧野草原13"
ab(13) = "牧野草原13,牧野草原12,牧野草原14,牧野草原02"
ab(14) = "牧野草原14,牧野草原03,牧野草原13,牧野草原18"
ab(15) = "牧野草原15,牧野草原18,牧野草原20"
ab(16) = "牧野草原16,牧野草原18,牧野草原20"
ab(17) = "牧野草原17,牧野草原12,牧野草原24"
ab(18) = "牧野草原18,牧野草原14,牧野草原24"
ab(19) = "牧野草原20,牧野草原15,牧野草原16,牧野草原26"
ab(20) = "牧野草原21,牧野草原22,牧野草原26"
ab(21) = "牧野草原22,牧野草原21,牧野草原32"
ab(22) = "牧野草原23,牧野草原09,牧野草原24,牧野草原33"
ab(23) = "牧野草原24,牧野草原17,牧野草原18,牧野草原23"
ab(24) = "牧野草原26,牧野草原20,牧野草原21,牧野草原30"
ab(25) = "牧野草原27,牧野草原25,牧野草原34"
ab(26) = "牧野草原28,牧野草原25,牧野草原34,牧野草原35"
ab(27) = "牧野草原30,牧野草原26,牧野草原31"
ab(28) = "牧野草原31,牧野草原30,牧野草原32"
ab(29) = "牧野草原32,牧野草原22,牧野草原31,牧野草原33"
ab(30) = "牧野草原33,牧野草原23,牧野草原32,牧野草原36"
ab(31) = "牧野草原34,牧野草原27,牧野草原28,牧野草原36"
ab(32) = "牧野草原35,牧野草原28,低矮林地"
ab(33) = "牧野草原36,牧野草原33,牧野草原34"
ab(34) = "万马草原_03,牧野草原06"
ab(35) = "低矮林地,牧野草原28"
上面是一个游戏中的地图的数据。地图一共有36个点,放在ab数组中,
split(ab(i),",")(0)是它的父结点,split(ab(i),",")(1-结束) 是它可以走到的临点, 问题是,我在这个图的任一点(StartWay)到结束的任何一点(EndWay),最近的一种走法,每次只能走一个点
问题补充:帮帮啦。OK再送50分 比如我现在的位置在 牧野草原04 即位置在ab(04)中
ab(4)(0)是点的位置,即 牧野草原04 它的临点,牧野草原06,牧野草原08,牧野草原10
也就是说。我在04可以走到06,08,10
这个函数可以取出,现在的位置所在,数组的第几位 Function ArrId(tem) As Integer
ArrId = -1
For ArrId_i = 0 To UBound(ab)
If Split(ab(ArrId_i), ",")(0) = tem Then
ArrId = ArrId_i
Exit For
End If
Next
End Function
个人对广度优先算法的理解是每次优先遍历父结点下的直接子结点,遍历完这些直接子结点之后再从这些子结点开始遍历他们的直接子结点,以此类推下去,直到找到终点。所以,此处肯定是需要使用到迭代了。在此我想写出我的思路来与楼主交流下。
1.确定startway点和endway点以后,找到startway点,并对该点下的子结点进行遍历。如你此处选择的startway是牧野草原04 即位置在ab(04),endway是牧野草原15,那么ab(04)下的直接子结点可认为是牧野草原06、牧野草原08和牧野草原10。我们开始按照广度优先算法遍历到牧野草原15。
2.首先我们遍历完04的子结点(06,08,10),发现没有15。
3.接下来我们遍历结点06的子结点(04,05,03),发现没有15.
4.然后,我们开始遍历结点08的子结点(4,15,16),发现15,于是整个遍历结束。
PS:对于回路的子结点不应该考虑遍历,比如06中04的回路。
麻烦各位。给写一下。
001安 定1450424908
002八坼站 007041600420406
003八 城114030540409203
004八 都1350922604
005摆渡口 0420303805
006百 花15103
007白龙桥 2150700204
008白 茆201042820809505
009板 桥0360319204
010宝 岩0190602804
011北 库0670608406
012北 桥26203
013碧 溪217082130428405
014兵 希2430513305
015曹安路 07005
016长 桥21907
017长 桥1280210006
018长 青13706
019常熟市 02704130040100611305
020车 坊09704
021陈 墓02908
022陈 塘191020270228703
023晨 阳2860423806
024慈 里1860209804
025磋 湾2520207703
026大 河28103
027大虹桥 022020190412003
028大 生010082421824805
029大 市1561802108
030大 新1260603205
031德 积23803
032店 岸03005
033淀 东19306
034董 浜129022470527505
035东 蔡0980214602
036东方红 2340400903
037东 岭159080790806704
038东 山077040050515504
039洞 泾25303
040东 张21703
041东 渚2050523007
042渡 村1340600503
043方 浜0560407404
044凤凰泾 210042180326203
045凤凰山 225031970428504
046浮 桥1650814803
047港 口1970419005
048工农兵桥1100324103
049共青大队0910527705
050共青圩 1230620203
051古 里2420420103
052光 福1080507802
053光 明2280207302
054归 庄0030422803
055涵 村2780218603
056河 东0660704303
057何 市12907
058横 泾1120513403
059横 泾1190214104
060横 谈204092590911803
061横 塘219032650922404
062红 旗17103
063洪 桥19602
064红 窑09107
065后 塍1950326706
066虎 丘089080560724513
067葫芦兜 037040940701106
068浒 浦213020140524603
069花 墩26104
070花家桥 23702
071华阳桥 142090270223009
072花 庄2720320702
073璜 泾0530226003
074黄 隶04304
075黄历桥 1760510403
076黄石桥 1750823407
077涧 桥0250303804
078涧上村 0520218203
079尖 田03708
080蒋 墩26102
081蒋 桥1110526806
082蒋 巷2490528103
083锦 丰1960416804
084金家坝 0110629107
085金 庭139022630627804
086泾 桥1360818104
087九 曲0920516503
088开弦弓 1180327610
089康 庄1730506608
090昆山东 241030910224305
091昆山市 09002049051430506407
092老闸站 0030308705
093蠡 口1090517202
094黎 里0670721603
095李 市00805
096粮管所 2690313203
097良 浦2340502002
098岭 东0240403502
099灵岩山 1540612202
100浏 河017061020410104
101浏河口 10004
102六里桥 2230310004
103芦 荡12404
104陆 渡0750312802
105陆 巷1550425202
106鹿 河26003
107陆家浜 1670323703
108路 口185040520515404
109陆 墓0930513702
110陆 扬114040480328306
111鹿 苑08105
112马家桥 1220505805
113毛家桥 0190523304
114毛沙塘 140030030311004
115梅 李21304275051910327206
116梅 埝1210512507
117棉种场 22908
118庙 港060130880313509
119妙 桥202020590218104
120淼 泉02703
121庙 头1160522611
122木 渎24605099021120522404
123南 丰1360305006
124南 桥174051030418805
125南湾桥 206051160716206
126南新街 2860203006
127南圩头 1720215804
128倪家桥 104020170226906
129年沙桥 280030340205707
130藕 渠0190417404
131庞湖农场1990321503
132牌 桥223060960326404
133蓬 郎01405
134浦 庄0580304206
135七 都1180900409
136七海坝 220030860612303
137齐 门109020180617505
138千 灯1930616406
139前 进1460408502
140前 进1630211403
141勤 丰05904
142青山咀 2450307109
143青阳港 0910516705
144青 云194052000513904
145青 州0010418403
146仇 巷03502
147任 阳2540214904
148日 新0460325602
149三泾口 1470416304
150三 洋27405
151沙 东187050060315301
152沙上村 249021570529004
153沙 溪1510127905
154善人桥 230051080409906
155尚 锦0380410504
156涉 浦0912002918
157沈 浜152052530327007
158沈 桥1270418004
159莘 塔03708
160胜 墩0020520605
161胜 浦21108
162盛 泽1250618307
163石 牌149041660514002
164石 浦13806
165时 思0870304608
166市潭泽 1880416305
167石头湾 1430510703
168十一圩 0830425005
169双山沙
170四号桥 250021980422004
171四一农场1980306203
172宋家楼 093021270221006
173宋 庄2110608905
174苏家翁 1300412405
175苏 州137050760821903
176太 北17803240060750517703
177太仓南 1760323503
178太仓市 2730417603
179太 湖18203
180太 平1580422708
181太平桥 086041190419703
182潭 东0780317903
183坛 丘16207
184潭 泽1450324402
185唐 村10804
186唐 里0550302402
187塘 桥2640425105
188唐 市1240516604
189塘 市2680822507
190塘 湾248020470520806
191塘 坐1150302202
192陶 浜0090425804
193陶家桥 0330613806
194桃 源14405
195套 闸2860406503
196天 福0630208304
197恬 庄181030450404704
198同 丰1700417103
199同 里2910513103
200铜 罗2760614405
201团结桥 0510300804
202团结村 0500311902
203万家宅 25602
204苑 平215120020606009
205望湖桥 2740304105
206望 桥21604160051250525902
207王 市0720228705
208王 庄19006
209卫 浜27004
210渭泾塘 172060440421204
211唯 亭289050160817306
212卫 星21004
213问 村013040680211504
214翁家庄 29004
215吴江市 25708131030070720412
216乌 桥0940320604
217吴 市247060130804003
218吴 塔2440404403
219吴中区 07503016070610325707
220西 港1700413603
221西界港 25005
222细 泾22709
223茜 泾256031020313206
224西跨塘 0610412204
225西 张1890704503
226夏家都 0040412111
227湘 城1800822209
228湘 里0540305302
229萧家桥 2330511708
230小茅山 041070710915405
231小桥头 26704
232斜 桥2680228605
233谢 桥287041130422905
234斜 塘076070360409705
235新 丰17703
236新 湖24003
237新 华1070307002
238新华侨 0230603103
239新 毛24003
240新毛站 25102239031760623603
241新 民0480309003
242新 桥0281805104
243新 镇090050140527306
244辛 庄1840221804
245兴贤桥 0661314203
246胥 口0690312205
247徐 市0340521706
248压路机 0280519002
249颜 港001080820515202
250雁行头 168051700222105
251杨林桥 2790624002
252杨 湾1050202502
253杨 园1570303903
254窑 场2550514702
255窑 镇279042540528205
256仪 桥148022030222303
257尹 山2190721508
258用 直19204
259油 库2060206009
260友谊桥 0730310603
261郁 舍0690408002
262袁家浜 0440301203
263元 山08506
264岳 王1320418704
265越 溪06109
266闸 上26809
267张家港 0650523104
268张家港市08106266091890823202
269张 桥1280609603
270张 桥1570720904
271张泗沟桥07102
272赵 市1150607203
273振 东2430617804
274镇 湖1500520503
275珍 门0340511505
276震 泽0881020006
277正 仪0490528902
278植 里0850405502
279直 塘153052510625504
280支 塘2820212903
281治 塘0820302603
282支塘站 255050080828002
283周 布11006
284周泾口 01305
285周家码头04504
286周家桥 23205023041260219504
287周 行022032070523304
288周 庄
289朱家村 2770221105
290练 塘1520421404
291屯 村0840719905
Begin VB.Form frmOSPF
Caption = "最短路径选择"
ClientHeight = 4650
ClientLeft = 3360
ClientTop = 2910
ClientWidth = 7170
Icon = "OSPF.frx":0000
LinkTopic = "Form2"
LockControls = -1 'True
ScaleHeight = 4650
ScaleWidth = 7170
Begin VB.TextBox Text1
Height = 3375
Left = 240
MultiLine = -1 'True
ScrollBars = 2 'Vertical
TabIndex = 5
Top = 1080
Width = 6735
End
Begin VB.CommandButton Command1
Caption = "打印最短路线"
Height = 495
Left = 4320
TabIndex = 4
Top = 360
Width = 2055
End
Begin VB.ComboBox Combo2
Height = 300
Left = 1680
TabIndex = 2
Text = "终点站"
Top = 600
Width = 1215
End
Begin VB.ComboBox Combo1
Height = 300
Left = 240
TabIndex = 1
Text = "起讫站"
Top = 600
Width = 1215
End
Begin VB.Label Label2
AutoSize = -1 'True
Caption = "终点站:"
Height = 180
Left = 1800
TabIndex = 3
Top = 240
Width = 720
End
Begin VB.Label Label1
AutoSize = -1 'True
Caption = "起讫站:"
Height = 180
Left = 240
TabIndex = 0
Top = 240
Width = 720
End
End
Attribute VB_Name = "frmOSPF"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = False
Attribute VB_PredeclaredId = True
Attribute VB_Exposed = False
Option Explicit
Dim start, ends As Long
Dim JLH(1 To 300), LJD(1 To 300, 1 To 4), DST(1 To 300, 1 To 4) As Long
Dim BH(1 To 300), ADD(1 To 300) As String
Dim n As Integer
Dim vertexnum As Integer
Dim edgenum As Integer
Const max = 100000
Dim graph(0 To 300, 0 To 300) As Long
Dim visited(0 To 300) As Integer
Dim path(0 To 300) As Integer
Dim distance(0 To 90000) As LongPrivate Function dijkstra(begin As Integer)
Dim minedge, vertex, i, j, n, m, edges As Integer
edges = 1
visited(begin) = 1
For i = 1 To vertexnum
distance(i) = graph(begin, i)
' Debug.Print distance(i)
Next i
distance(begin) = 0
While (edges < vertexnum - 1)
edges = edges + 1
minedge = max
For j = 1 To vertexnum
If visited(j) = 0 And minedge > distance(j) Then
vertex = j
minedge = distance(j)
End If
Next j
visited(vertex) = 1
For n = 1 To vertexnum
If visited(n) = 0 And (distance(vertex) + graph(vertex, n)) < distance(n) Then
distance(n) = distance(vertex) + graph(vertex, n)
path(n) = vertex
End If
Next
Wend
End Function
Private Sub Command1_Click()
Dim i, j As Integer
Dim k As Integer
Dim addname(1 To 100) As String
Text1 = ""
If start = 0 Or ends = 0 Then
MsgBox "请选择起始站与终点站"
Exit Sub
End If
For i = 1 To vertexnum
visited(i) = 0
path(i) = 1
Next
dijkstra (start)
Text1 = "起讫站:" & ADD(start) & " --> " & "终点站:" & ADD(ends) & vbCrLf
Text1 = Text1 & vbCrLf
If distance(ends) = max Then
Text1 = Text1 & "两站点间没有可联接的路线!"
Exit Sub
Else
Text1 = Text1 & "它们之间的距离为: " & distance(ends) * 0.1 & " Km" & vbCrLf
Text1 = Text1 & vbCrLf
Text1 = Text1 & "它们之间的最短路线为:" & vbCrLf
Text1 = Text1 & vbCrLf
Text1 = Text1 & ADD(start)
End If
k = ends
j = 1
Do
addname(j) = ADD(k)
k = path(k)
j = j + 1
Loop While (k <> 1)
For j = j - 1 To 1 Step -1
Text1 = Text1 & "--> " & addname(j)
Next j
End SubPrivate Sub Form_Initialize()
Dim i, j, k As Long
Dim filename As String
Dim buffers As String
On Error Resume Next
filename = App.path + "\" + "Add_Dst" + ".txt"
Open filename For Input As #1
If LOF(1) = 0 Then
MsgBox "The lenth of the file is zero! Please Select it asgain。" & vbCrLf & "The file name is Add_Dst。"
Exit Sub
End If
i = 1
Do While Not EOF(1)
Line Input #1, buffers
BH(i) = Val(Mid$(buffers, 1, 3))
ADD(i) = Mid$(buffers, 4, 4)
Combo1.AddItem ADD(i)
Combo2.AddItem ADD(i)
LJD(i, 1) = Val(Mid$(buffers, 8, 3)) '邻接点的编号
DST(i, 1) = Val(Mid$(buffers, 11, 2)) '与邻接点之间的距离
LJD(i, 2) = Val(Mid$(buffers, 13, 3))
DST(i, 2) = Val(Mid$(buffers, 16, 2))
LJD(i, 3) = Val(Mid$(buffers, 18, 3))
DST(i, 3) = Val(Mid$(buffers, 21, 2))
LJD(i, 4) = Val(Mid$(buffers, 24, 3))
DST(i, 4) = Val(Mid$(buffers, 27, 2))
Kill buffers
i = i + 1
Loop
n = i - 1
' Debug.Print n
Close #1
vertexnum = n '设置图的顶点数
edgenum = 0
For i = 1 To n
For j = 1 To 4
If LJD(i, j) = 0 Then Exit For
edgenum = edgenum + 1 '获得图的边数
graph(i, LJD(i, j)) = DST(i, j) '从i点与其邻接点LJD(i,j)的距离
Next
Next For i = 0 To n
For j = 0 To n
If graph(i, j) = 0 Then
graph(i, j) = max
End If
Next
Next
End Sub
Private Sub Combo1_click()
start = Combo1.ListIndex + 1 '获得起讫站的编号
End SubPrivate Sub Combo2_click()
ends = Combo2.ListIndex + 1 '获得终点站的编号
End Sub
DST(i, 1) = Val(Mid$(buffers, 11, 2)) '与邻接点之间的距离
LJD(i, 2) = Val(Mid$(buffers, 13, 3)) '?????????这几个点是?
DST(i, 2) = Val(Mid$(buffers, 16, 2)) '?????????这几个点是?
LJD(i, 3) = Val(Mid$(buffers, 18, 3)) '?????????这几个点是?
DST(i, 3) = Val(Mid$(buffers, 21, 2)) '?????????这几个点是?
LJD(i, 4) = Val(Mid$(buffers, 24, 3)) '?????????这几个点是?
DST(i, 4) = Val(Mid$(buffers, 27, 2)) '?????????这几个点是?
001安 定1450424908
002八坼站 007041600420406
003八 城114030540409203
要把点换成ID
001牧野草原00 牧野草原01,牧野草原05,牧野草原07