注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

我的博客

 
 
 

日志

 
 

操作系统实验报告——dijkstra算法  

2007-12-05 23:29:33|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

实验名称:编写程序实现路由算法----dijkstra算法寻路过程的演示

实验目的:了解路由器的路由原理和寻路过程,复习dijkstra算法求最短路径的原理和寻路的过程。                                                                    

实验要求:用可视化图形界面实现演示过程,能够正确地显示出求最短路径的过程。并标出到每个点的长度和所经过的节点。

实验分析:dijlstra算法描述:(1)用带权的邻接矩阵来表示带权的有向图d[i][j]表示弧<v,u>的权值,若不存在,则置999S为已找到从v出发的最短路径的终点的集合,它的初态为空集。(2)选择v使得d[j]=min{d[j]|vV-S集合中}v就是当前求得的一条从u出发的最短路径的终点。令S=S并上{j}。(3)修改从u出发到集合V-S上任意一顶点v可达的最短路径长度如果d[j]+arcs[j][k]<d[k],则修改d[k]d[k]=d[j]+arcs[j][k].4)重复操作(2)(3)共n-1次。由此求得从u到图上其余各顶点的最短路径是依路径长度递增的序列。

程序流程图:

              

实验心得:这是自己第一次用vb写的程序,当运行完后,能看见运行结果,且是正确的,心里很高兴,上次周老师说得没错,vb要比vc好学一些,很快就能够上手,且我听了一些网上的课程,边听自己边照着写代码,加上vb是可视化界面设计,很多东西很快就记住了,但因为学习时间不是很长,所以写的程序不是很规范,也不是很简洁,对有些控件的应用还不熟练,我正在看这方面的书籍,相信下次我会做得更好。

实验参考书:《计算机网络(第四版)》

              VB程序设计教程》

              《数据结构》

实验代码:

Private Declare Sub Sleep Lib "kernel32" (ByVal dwmilliseconds As Integer)

 

Private Type vertex

a As Integer

b As Integer

x As Integer

y As Integer

flag As Integer

End Type

 

Dim v(1 To 8) As vertex

Dim d(1 To 8, 1 To 8)

Dim i, j As Integer

 

Private Sub Command1_Click()

Picture1.DrawWidth = 8

For i = 1 To 8

    Picture1.PSet (v(i).x, v(i).y)

Next i

Picture1.DrawWidth = 1

Picture1.Line (v(1).x, v(1).y)-(v(2).x, v(2).y)

Picture1.Line (v(1).x, v(1).y)-(v(7).x, v(7).y)

Picture1.Line (v(2).x, v(2).y)-(v(3).x, v(3).y)

Picture1.Line (v(2).x, v(2).y)-(v(5).x, v(5).y)

Picture1.Line (v(3).x, v(3).y)-(v(4).x, v(4).y)

Picture1.Line (v(3).x, v(3).y)-(v(6).x, v(6).y)

Picture1.Line (v(4).x, v(4).y)-(v(8).x, v(8).y)

Picture1.Line (v(5).x, v(5).y)-(v(6).x, v(6).y)

Picture1.Line (v(5).x, v(5).y)-(v(7).x, v(7).y)

Picture1.Line (v(6).x, v(6).y)-(v(8).x, v(8).y)

Picture1.Line (v(7).x, v(7).y)-(v(8).x, v(8).y)

 

Print: Print: Print: Print

Print: Print: Print: Print

Print: Print: Print: Print

Print: Print: Print: Print

Print: Print

Print " route";

Print Space(25);

Print "length"

End Sub

 

Private Sub Command2_Click()

Dim k, t, m, r, q As Integer

Picture1.DrawWidth = 6

Picture1.PSet (v(1).x, v(1).y), RGB(255, 0, 0)

i = 1

perfer: For j = 1 To 8

            If d(i, j) <> 999 And v(j).flag <> 1 _

            And v(j).a > (v(i).a + d(i, j)) Then

               v(j).a = v(i).a + d(i, j)

               v(j).b = i

            End If

        Next j

m = 0

t = 999

For k = 2 To 8

    If v(k).flag <> 1 Then

       If v(k).a < t Then

         m = k

         t = v(k).a

       End If

    End If

Next k

If m <> 0 Then

  v(m).flag = 1

  d(v(m).b, m) = 999

  d(m, v(m).b) = 999

  Picture1.DrawWidth = 6

  Sleep 1000

  Picture1.PSet (v(m).x, v(m).y), RGB(255, 0, 0)

  Sleep 1000

  Picture1.DrawWidth = 2

  Picture1.Line (v(v(m).b).x, v(v(m).b).y)-(v(m).x, v(m).y), RGB(0, 255, 0)

  r = m

  q = 1

  While r > 1

       Print r;

       Print "<-";

       r = v(r).b

       q = q + 1

  Wend

  Print 1;

  Print Space(35 - 5 * q);

  Print v(m).a

  For k = 2 To 8

    If v(k).flag <> 1 Then

       i = m

       GoTo perfer

    End If

  Next k

End If

End Sub

 

Private Sub Form_Load()

For i = 1 To 8

    For j = 1 To 8

        d(i, j) = 999

    Next j

Next i

  d(1, 2) = 2: d(2, 1) = 2

  d(1, 7) = 6: d(7, 1) = 6

  d(2, 3) = 7: d(3, 2) = 7

  d(2, 5) = 2: d(5, 2) = 2

  d(3, 4) = 3: d(4, 3) = 3

  d(3, 6) = 3: d(6, 3) = 3

  d(4, 8) = 2: d(8, 4) = 2

  d(5, 6) = 2: d(6, 5) = 2

  d(5, 7) = 1: d(7, 5) = 1

  d(6, 8) = 2: d(8, 6) = 2

  d(7, 8) = 4: d(8, 7) = 4

  v(1).a = 0

  v(1).b = 1

  v(1).flag = 1

For i = 2 To 8

    v(i).a = 999

    v(i).flag = 0

Next i

v(1).x = 1000: v(1).y = 1700

v(2).x = 1500: v(2).y = 1000

v(3).x = 3500: v(3).y = 1000

v(4).x = 4000: v(4).y = 1700

v(5).x = 2000: v(5).y = 1700

v(6).x = 3000: v(6).y = 1700

v(7).x = 1500: v(7).y = 2400

v(8).x = 3500: v(8).y = 2400

End Sub

实验结果显示:

  评论这张
 
阅读(361)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017