永发信息网

Dijkstrath算法是什么?如何用Dijkstrath算法求计算机网络拓扑图的最短路径?

答案:3  悬赏:80  手机版
解决时间 2021-03-26 06:58
  • 提问者网友:藍了天白赴美
  • 2021-03-25 10:04
Dijkstrath算法是什么?如何用Dijkstrath算法求计算机网络拓扑图的最短路径?
最佳答案
  • 五星知识达人网友:封刀令
  • 2021-03-25 10:22
应该是Dijkstra算法 你百度这个能查到
不涉及什么数学知识 会加法和比较大小就行追问用这个来求网络拓扑图的最短路径复杂吗?追答不复杂 但用floyd更简单 就三个循环 但时间复杂度高一些追问您可以随便起道求网络拓扑图的题目给我看看吗?还有解题步骤、谢谢 ^ ^
全部回答
  • 1楼网友:枭雄戏美人
  • 2021-03-25 11:30
就是啊是Dijkstra,不涉及数学知识,要是确实要跟数学车上关系的话,那就是运筹学,这个里面有讲。追问用这个来求网络拓扑图的最短路径复杂吗?
  • 2楼网友:不想翻身的咸鱼
  • 2021-03-25 11:04
Dijkstra算法是典型 的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
 迪杰斯特拉(Dijkstra)算法思想  
按路径长度递增次序产生最短路径算法:
  把V分成两组:
  (1)S:已求出最短路径的顶点的集合
  (2)V-S=T:尚未确定最短路径的顶点集合
  将T中顶点按最短路径递增的次序加入到S中,
  保证:(1)从源点V0到S中各顶点的最短路径长度都不大于
  从V0到T中任何顶点的最短路径长度
  (2)每个顶点对应一个距离值
  S中顶点:从V0到此顶点的最短路径长度
  T中顶点:从V0到此顶点的只包括S中顶点作中间
  顶点的最短路径长度
  依据:可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的
  直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和
  (反证法可证)
  求最短路径步骤
  算法步骤如下:
  1. 初使时令 S={V0},T={其余顶点},T中顶点对应的距离值
  若存在,d(V0,Vi)为弧上的权值
  若不存在,d(V0,Vi)为∝
  2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S
  3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的
  距离值缩短,则修改此距离值
  重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
点此我要举报以上问答信息
大家都在看
推荐资讯