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

Question

要用Dijkstrath算法求拓扑图的最短路径，要涉及到数学中的什么知识啊？ 这是考试的一个要点，我数学很差，百度了一下完全看不到，希望在这里能有大神帮帮我，谢谢

Answer 1

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中顶点对应的距离值

　　若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

　　若不存在<V0,Vi>，d(V0,Vi)为∝

　　2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S

　　3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的

　　距离值缩短，则修改此距离值

　　重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

Answer 2

应该是Dijkstra算法 你百度这个能查到
不涉及什么数学知识 会加法和比较大小就行追问

用这个来求网络拓扑图的最短路径复杂吗？

追答

不复杂 但用floyd更简单 就三个循环 但时间复杂度高一些

追问

您可以随便起道求网络拓扑图的题目给我看看吗？还有解题步骤、谢谢 ^ ^

本回答被网友采纳

Answer 3

就是啊是Dijkstra，不涉及数学知识，要是确实要跟数学车上关系的话，那就是运筹学，这个里面有讲。追问

用这个来求网络拓扑图的最短路径复杂吗？