求解:图论中常见的最短路径算法有几种?都是什么?
发布网友
发布时间：2022-04-25 22:37
共2个回答
热心网友
时间：2022-06-18 06:32
算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下五个重要的特征：
1、有穷性： 一个算法必须保证执行有限步之后结束；
2、确切性： 算法的每一步骤必须有确切的定义；
3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
算法的设计要求
1）正确性（Correctness）
有4个层次：
A．程序不含语法错误；
B．程序对几组输入数据能够得出满足规格要求的结果；
C．程序对精心选择的、典型的、苛刻的、带有刁难性的几组输入数据能够得出满足规格要求的结果；
D．程序对一切合法的输入数据都能产生满足规格要求的结果。
2）可读性（Readability）
算法的第一目的是为了阅读和交流；
可读性有助于对算法的理解；
可读性有助于对算法的调试和修改。
3）高效率与低存储量
处理速度快；存储容量小
时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的统一、折中。
算法的描述 算法的描述方式（常用的）
算法描述 自然语言
流程图 特定的表示算法的图形符号
伪语言 包括程序设计语言的三大基本结构及自然语言的一种语言
类语言 类似高级语言的语言，例如，类PASCAL、类C语言。
算法的评价 算法评价的标准：时间复杂度和空间复杂度。
1）时间复杂度 指在计算机上运行该算法所花费的时间。用“O（数量级）”来表示，称为“阶”。
常见的时间复杂度有： O（1）常数阶；O（logn）对数阶；O（n）线性阶；O（n＾2）平方阶
2）空间复杂度 指算法在计算机上运行所占用的存储空间。度量同时间复杂度。
时间复杂度举例
（a） X：=X+1 ； O（1）
（b） FOR I：=1 TO n DO
X：= X+1； O（n）
（c） FOR I：= 1 TO n DO
FOR J：= 1 TO n DO
X：= X+1； O（n＾2）
“算法”一词最早来自公元 9世纪 波斯数学家比阿勒·霍瓦里松的一本影响深远的著作《代数对话录》。20世纪的 英国 数学家 图灵 提出了著名的图灵论点，并抽象出了一台机器，这台机器被我们称之为 图灵机 。图灵的思想对算法的发展起到了重要的作用。
算法是 计算机 处理信息的本质，因为 计算机程序 本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。 一般地，当算法在处理信息时，数据会从输入设备读取，写入输出设备，可能保存起来以供以后使用。
这是算法的一个简单的例子。
我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小 可以将下面的算法形象地称为“捡豆子”：
首先将第一颗豆子（数列中的第一个数字）放入口袋中。
从第二颗豆子开始检查，直到最后一颗豆子。如果正在检查的豆子比口袋中的还大，则将它捡起放入口袋中，同时丢掉原先的豆子。 最后口袋中的豆子就是所有的豆子中最大的一颗。
下面是一个形式算法，用近似于 编程语言 的 伪代码 表示
给定：一个数列“list"，以及数列的长度"length(list)" largest = list[1] for counter = 2 to length(list): if list[counter] > largest: largest = list[counter] print largest
符号说明:
= 用于表示赋值。即：右边的值被赋予给左边的变量。
List[counter] 用于表示数列中的第 counter 项。例如：如果 counter 的值是5，那么 List[counter] 表示数列中的第5项。
<= 用于表示“小于或等于”。
算法的分类
（一）基本算法 :
1.枚举
2.搜索:
深度优先搜索
广度优先搜索
启发式搜索
遗传算法
（二）数据结构的算法
（三）数论与代数算法
（四）计算几何的算法：求凸包
（五）图论 算法：
1.哈夫曼编码
2.树的遍历
3.最短路径 算法
4.最小生成树 算法
5.最小树形图
6.网络流 算法
7.匹配算法
（六）动态规划
（七）其他：
1.数值分析
2.加密算法
3.排序 算法
4.检索算法
5.随机化算法
参考资料：百度一下
热心网友
时间：2022-06-18 06:33
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、
