以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 Dot NET,C#,ASP,VB 』  (http://bbs.xml.org.cn/list.asp?boardid=43)
----  [求助] 哪位达人指导一下关于 最短路径dijkstra的VB算法(修改程序)  (http://bbs.xml.org.cn/dispbbs.asp?boardid=43&rootid=&id=19154)


--  作者:sky_kiss
--  发布时间:6/2/2005 3:59:00 PM

--  [求助] 哪位达人指导一下关于 最短路径dijkstra的VB算法(修改程序)
毕业设计 很着急,谢谢`请指导一下
它还有一个关于地图信息的资料 请联系我 不胜感激  QQ33237884 MSN:fm2323556@hotmail.com
想把这个程序修改的简单一点 就是只有7-9个点的图
原程序如下:

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 Long

Private 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 Sub

Private 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 Sub

Private Sub Combo2_click()
    ends = Combo2.ListIndex + 1      '获得终点的编号
End Sub

Private Sub Text1_Change()

End Sub


下面还有个就是相当于站点的编号:
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


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
93.994ms