下载文档原格式
什么是伪代码？
伪代码（Pseudocode）是一种算法描述语言。
使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。
因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。
介于自然语言与编程语言之间。
例如，类Pascal语言的伪代码的语法规则是：在伪代码中，每一条指令占一行（else if，例外）。
指令后不跟任何符号（Pascal和C中语句要以分号结尾）。
书写上的“缩进”表示程序中的分支程序结构。
这种缩进风格也适用于if-then-else语句。
用缩进取代传统Pascal中的begin和end语句来表示程序的块结构可以大大提高代码的清晰性；同一模块的语句有相同的缩进量，次一级模块的语句相对与其父级模块的语句缩进。
伪代码只是像流程图一样用在程序设计的初期，帮助写出程序流程。
简单的程序一般都不用写流程、写思路，但是复杂的代码，最好还是把流程写下来，总体上去考虑整个功能如何实现。
写完以后不仅可以用来作为以后测试,维护的基础，还可用来与他人交流。
但是，如果把全部的东西写下来必定可能会让费很多时间，那么这个时候可以采用伪代码方式。
比如：
IF 九点以前 THEN
do 私人事务；
ELSF 9点到18点 THEN
工作；
ELSE
下班;
END IF
这样不但可以达到文档的效果,同时可以节约时间. 更重要的是,使结构比较清晰,表达方式更加直观.。
算法的概念与伪代码的使用·算法 Algorithm算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。
通俗点说，就是计算机解题的过程。
在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。
前者是推理实现的算法，后者是操作实现的算法。
一个算法应该具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束；确切性：算法的每一步骤必须有确切的定义；输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
没有输出的算法是毫无意义的；可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。
Did you knowAlgorithm 一词的由来Algorithm(算法)一词本身就十分有趣。
初看起来，这个词好像是某人打算要写"Logarithm"(对数)一词但却把头四个字母写的前后颠倒了。
这个词一直到1957年之前在Webster's New World Dictionary(《韦氏新世界词典》)中还未出现，我们只能找到带有它的古代涵义的较老形式的"Algorism"(算术)，指的是用阿拉伯数字进行算术运算的过程。
在中世纪时，珠算家用算盘进行计算，而算术家用算术进行计算。
中世纪之后，对这个词的起源已经拿不准了，早期的语言学家试图推断它的来历，认为它是从把algiros(费力的)+arithmos(数字)组合起来派生而成的，但另一些人则不同意这种说法，认为这个词是从"喀斯迪尔国王Algor"派生而来的。
最后，数学史学家发现了algorism(算术)一词的真实起源：它来源于著名的Persian Textbook(《波斯教科书》)的作者的名字Abu Ja'far Mohammed ibn M?sa al-Khowarizm （约公元前825年）--从字面上看，这个名字的意思是"Ja'far 的父亲，Mohammed 和 M?sa 的儿子，Khowarizm 的本地人"。
伪代码基本语法伪代码基本语法指的是一种近似于编程语言的描述性语言，用于描述算法或程序逻辑。
它不是一种具体的编程语言，而是一种简化的、类似于人类语言的抽象描述方式。
它的语法规则相对简单明了，以下将介绍伪代码基本语法的一些重要要点。
1. 注释在伪代码中，注释用来解释代码的功能或作用，以便其他人理解。
注释通常以“//”或“#”开头，表示单行注释；以“/*”开头，以“*/”结尾，表示多行注释。
2. 变量在伪代码中，变量用于存储数据，并可以通过赋值操作进行修改。
变量的命名应具有描述性，以便于理解。
变量的类型可以是整数、浮点数、字符串等。
变量的赋值使用“=”符号。
3. 输入和输出伪代码中的输入使用“输入”关键字，输出使用“输出”关键字。
例如：输入：从键盘读取一个整数输出：将结果打印到屏幕上4. 条件语句伪代码中的条件语句用于根据不同的条件执行不同的操作。
常见的条件语句有if语句和switch语句。
if语句根据条件判断是否执行某段代码，switch语句根据不同的条件执行不同的代码块。
5. 循环语句伪代码中的循环语句用于重复执行一段代码。
常见的循环语句有for循环、while循环和do-while循环。
for循环用于指定循环次数的情况，while循环用于根据条件判断是否继续循环，do-while 循环先执行一次循环体，然后再根据条件判断是否继续循环。
6. 数组伪代码中的数组用于存储一组相同类型的数据。
数组可以通过索引来访问和修改其中的元素。
数组的索引从0开始。
7. 函数伪代码中的函数用于封装一段可重用的代码。
函数可以接受参数并返回结果。
函数的定义通常包括函数名、参数列表和返回值类型。
8. 模块化伪代码中的模块化用于将程序分解成多个模块，每个模块负责完成特定的任务。
模块化可以提高代码的可读性和可维护性。
9. 错误处理伪代码中的错误处理用于处理可能出现的错误或异常情况。
错误处理可以使用条件语句或异常处理机制来处理。
中文算法伪代码概述在计算机科学中，算法是解决问题的方法和步骤的描述，而伪代码则是一种类似于编程语言的抽象描述方式。
中文算法伪代码指的是用中文语言描述算法的伪代码，相比其他语言的伪代码，它更便于理解和使用。
本文将从以下几个方面详细探讨中文算法伪代码。
为什么需要中文算法伪代码对于非专业的程序员或计算机科学领域的新手来说，掌握一门编程语言的语法和规则可能是一项具有挑战性的任务。
而使用中文算法伪代码，可以将复杂的编程概念用更简单易懂的中文语言进行描述，极大地降低了学习和理解的难度。
此外，中文算法伪代码还可以方便非程序员之间的沟通和交流，使得更多人能够参与到算法设计和问题解决中。
中文算法伪代码的语法规则中文算法伪代码的语法规则主要包括以下几个方面：关键字与其他编程语言类似，中文算法伪代码也有一些关键字用来表示不同的操作和控制结构，例如「如果」、「那么」、「否则」等。
这些关键字用来描述算法的逻辑流程和条件判断。
注释中文算法伪代码的注释使用「注释：」关键字进行标识，以帮助读者理解代码的意图和目的。
注释可以用来解释算法中的特殊处理或者对某段代码的说明。
变量和赋值中文算法伪代码可以使用中文词语作为变量名，程序员可以根据实际情况选择合适的命名方式。
赋值操作使用「赋值给」的关键字进行表示，例如「x 赋值给 5」表示将 x 的值设置为 5。
控制结构中文算法伪代码支持常见的控制结构，例如条件判断、循环和函数定义等。
条件判断使用「如果」、「那么」和「否则」关键字进行表示；循环使用「重复」和「直到」关键字进行表示；函数定义使用「定义」和「为」关键字进行表示。
函数调用中文算法伪代码可以使用函数调用来实现代码的模块化和重用。
函数调用使用「调用」和「函数名」进行表示，例如「调用求和函数」表示调用名为「求和函数」的函数。
示例中文算法伪代码下面是一个计算斐波那契数列的算法的示例中文算法伪代码：从键盘输入一个正整数 n如果 n 小于等于 0则输出错误信息并结束否则定义函数求斐波那契数列如果 n 等于 1 或者 n 等于 2则返回 1否则返回求斐波那契数列(n-1) 加上求斐波那契数列(n-2)调用求斐波那契数列函数并输出结果结束在以上示例中，使用了中文关键字来描述算法的逻辑流程，使得代码更加易懂。
克鲁斯卡尔算法伪代码克鲁斯卡尔算法是一个用于求解最小生成树的算法。
最小生成树(Minimum Spanning Tree, MST)指的是在一张无向图G中找到一个树T，使得T中的边权之和最小。
克鲁斯卡尔算法的基本思路是将所有边按照权值从小到大排序，然后依次选取这些边，如果选取的边之间没有形成环，就将该边加入到最小生成树中去。
这样，直到最小生成树中有n-1条边为止，就得到了最小生成树。
1. 将边按照权值从小到大排序。
2. 初始化一个并查集，即每个点都是一个单独的子集。
3. 遍历排好序的边，依次将边加入最小生成树中。
4. 对于每条边，检查该边的两个端点是否在同一个子集中，如果不在同一个子集中，则将它们合并成一个子集，同时将这条边加入最小生成树中。
5. 直到最小生成树中有n-1条边为止。
下面是使用Java语言实现克鲁斯卡尔算法的代码示例：//边的类定义class Edge implements Comparable<Edge> {int u; // 边的起点int v; // 边的终点int w; // 边的权值// 构造函数public Edge(int u, int v, int w) {this.u = u;this.v = v;this.w = w;}//并查集的类定义class UnionFind {int[] parent;int[] rank;//查找父节点public int find(int p) {while (p != parent[p]) {parent[p] = parent[parent[p]]; //路径压缩p = parent[p];}return p;}//判断两个节点是否在同一个集合中public boolean connected(int p, int q) {return find(p) == find(q);}}//求解最小生成树public void solve() {Collections.sort(edges); //按照权值从小到大排序UnionFind uf = new UnionFind(V); //初始化并查集Kruskal kruskal = new Kruskal(V, edges);kruskal.solve();System.out.println("最小生成树的边为：");for (Edge e : kruskal.mst) {System.out.println(e.u + " - " + e.v + " : " + e.w);}}输出结果如下：最小生成树的边为： 0 - 2 : 13 - 5 : 21 - 4 : 30 - 1 : 62 -3 : 5。
动量算法的伪代码
动量算法是一种常用于优化问题的迭代算法。
它模拟了物理学中的动量概念，通过考虑上一次迭代的方向和速度来指导下一次迭代的方向和速度。
下面是动量算法的伪代码：
初始化参数：
learning_rate = 0.01 # 学习率
momentum = 0.9 # 动量因子
iterations = 1000 # 迭代次数
初始化变量：
velocity = 0 # 初始速度
对于每次迭代：
计算梯度：
gradient = compute_gradient(parameters)
更新速度：
velocity = momentum * velocity - learning_rate * gradient
更新参数：
parameters = parameters + velocity
返回最优参数
以上是动量算法的伪代码。
在每次迭代中，我们首先计算梯度，然后根据当前速度和梯度更新速度。
最后，根据更新后的速度更新参数。
这样，通过考虑历史速度信息，动量算法可以帮助我们更快地收敛到最优解。
动量算法在优化问题中广泛应用，特别是在深度学习中。
它可以帮助我们在复杂的优化空间中更好地搜索并找到最优解。
通过使用动量算法，我们可以更快地训练神经网络，并提高其性能。
动量算法是一种有效的优化算法，它通过模拟物理学中的动量概念来指导优化过程。
它能够加速收敛并提高优化结果的质量。
在实际应用中，我们可以根据问题的特点来调整学习率和动量因子，以获得更好的优化效果。
算法流程图及算法的伪代码描述下载温馨提示:该文档是我店铺精心编制而成，希望大家下载以后，能够帮助大家解决实际的问题。
文档下载后可定制随意修改，请根据实际需要进行相应的调整和使用，谢谢!并且，本店铺为大家提供各种各样类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，如想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by theeditor. I hope that after you download them,they can help yousolve practical problems. The document can be customized andmodified after downloading,please adjust and use it according toactual needs, thank you!In addition, our shop provides you with various types ofpractical materials,such as educational essays, diaryappreciation,sentence excerpts,ancient poems,classic articles,topic composition,work summary,word parsing,copy excerpts,other materials and so on,want to know different data formats andwriting methods,please pay attention!一、冒泡排序算法流程图1. 开始2. 输入待排序的数组3. 设置外层循环，控制排序轮数4. 设置内层循环，控制每轮比较次数5. 比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置6. 重复步骤 5，直到内层循环结束7. 重复步骤 3-6，直到外层循环结束8. 输出排序后的数组9. 结束二、冒泡排序算法的伪代码描述```输入：待排序的数组 A输出：排序后的数组 A1. 开始2. for i = 1 to n-1 do3. for j = 1 to n-i do4. if A[j] > A[j+1] then5. 交换 A[j] 和 A[j+1]6. end if7. end for8. end for9. 输出 A10. 结束```三、注意事项1. 冒泡排序是一种简单的排序算法，但它的效率较低，在实际应用中通常不被使用。
伪代码描述算法算法标题：最小生成树（Prim算法）在图论中，最小生成树是指在一个连通图中找出一棵包含所有顶点且权值最小的树。
Prim算法是一种常用的解决最小生成树问题的算法。
1. 算法思想Prim算法的核心思想是以一个顶点为起点，逐步扩展生成最小生成树。
具体步骤如下：- 首先选取一个起始顶点，将其加入最小生成树的集合中。
- 然后，从与起始顶点相连的边中选择一条权值最小的边，并加入最小生成树的集合中。
- 接着，从已选取的边所连接的顶点中，选择一条权值最小的边，并加入最小生成树的集合中。
- 重复上述步骤，直到最小生成树的集合包含了所有顶点。
2. 算法实现下面通过伪代码来描述Prim算法的实现过程：```Prim(G, s):初始化集合V为图G的所有顶点初始化集合S为空，用于存放最小生成树的顶点集合初始化集合E为空，用于存放最小生成树的边集合将起始顶点s加入集合S中重复以下步骤，直到集合S包含了所有顶点：从集合V-S中选择一条连接到集合S中的顶点的权值最小的边(u, v)将顶点v加入集合S中将边(u, v)加入集合E中返回最小生成树的边集合E```3. 算法示例下面通过一个示例图来演示Prim算法的具体执行过程。
```输入：图G(V, E)，其中V为顶点集合，E为边集合输出：最小生成树的边集合E1. 初始化集合V为{A, B, C, D, E, F, G, H}初始化集合S为空，用于存放最小生成树的顶点集合初始化集合E为空，用于存放最小生成树的边集合2. 将起始顶点A加入集合S中3. 重复以下步骤，直到集合S包含了所有顶点：- 从集合V-S中选择一条连接到集合S中的顶点的权值最小的边(u, v)- 将顶点v加入集合S中- 将边(u, v)加入集合E中第一次循环：- 选择边(A, B)，将顶点B加入集合S中，将边(A, B)加入集合E 中第二次循环：- 选择边(B, D)，将顶点D加入集合S中，将边(B, D)加入集合E 中第三次循环：- 选择边(D, C)，将顶点C加入集合S中，将边(D, C)加入集合E 中第四次循环：- 选择边(C, F)，将顶点F加入集合S中，将边(C, F)加入集合E 中第五次循环：- 选择边(F, E)，将顶点E加入集合S中，将边(F, E)加入集合E 中第六次循环：- 选择边(E, G)，将顶点G加入集合S中，将边(E, G)加入集合E中第七次循环：- 选择边(G, H)，将顶点H加入集合S中，将边(G, H)加入集合E中4. 返回最小生成树的边集合E，即{(A, B), (B, D), (D, C), (C, F), (F,E), (E, G), (G, H)}```4. 算法分析- 时间复杂度：Prim算法的时间复杂度为O(|V|^2)，其中|V|为顶点的数量。
算法分析与设计伪代码大全在此，我们提供一个算法分析与设计伪代码的实现示例，包括常用的排序算法、查找算法、图算法等。
请注意，由于字数限制，下方的示例并不会涵盖所有可能的算法伪代码。
1.排序算法1.1 冒泡排序（Bubble Sort）```procedure bubbleSort(A: array of integers)for i from 0 to length(A) - 2for j from 0 to length(A) - i - 2if A[j] > A[j + 1] thenswap A[j] and A[j + 1]end ifend forend forend procedure```1.2 选择排序（Selection Sort）```procedure selectionSort(A: array of integers) for i from 0 to length(A) - 2smallestIndex = ifor j from i + 1 to length(A) - 1if A[j] < A[smallestIndex] thensmallestIndex = jend ifend forif smallestIndex != i thenswap A[i] and A[smallestIndex]end ifend forend procedure```1.3 插入排序（Insertion Sort）```procedure insertionSort(A: array of integers) for i from 1 to length(A) - 1key = A[i]j=i-1while j >= 0 and A[j] > keyA[j+1]=A[j]j=j-1end whileA[j + 1] = keyend forend procedure```2.查找算法2.1 顺序查找（Sequential Search）```function sequentialSearch(A: array of integers, target: integer): booleanfor i from 0 to length(A) - 1if A[i] = target thenreturn trueend ifend forend function```2.2 二分查找（Binary Search）```function binarySearch(A: array of integers, target: integer): booleanlow = 0high = length(A) - 1while low <= highmid = (low + high) / 2if A[mid] = target thenreturn trueelse if A[mid] < target thenlow = mid + 1elsehigh = mid - 1end ifend whileend function```3.图算法3.1 广度优先（Breadth-First Search）```procedure breadthFirstSearch(G: graph, startVertex: vertex) create empty queue Qcreate empty visited set Senqueue startVertex into Qadd startVertex to Swhile Q is not emptycurrent = dequeue Qprocess currentfor each neighbor of currentif neighbor is not in Sadd neighbor to Senqueue neighbor into Qend ifend forend whileend procedure```3.2 深度优先（Depth-First Search）```procedure depthFirstSearch(G: graph, startVertex: vertex) create empty visited set SdfsHelper(G, startVertex, S)end procedureprocedure dfsHelper(G: graph, currentVertex: vertex, visitedSet: set of vertices)add currentVertex to visitedSetprocess currentVertexfor each neighbor of currentVertexif neighbor is not in visitedSetdfsHelper(G, neighbor, visitedSet)end ifend forend procedure```这里提供的伪代码示例只是一部分常用算法的示例，你可以根据实际需要调整算法的实现。
《算法导论》中伪代码的约定1.书上代码的“缩进”表⽰程序中的分程序（程序块）结构如下所⽰：A1@@@@@@@@@@@@@@@@@@@*********************************************C1############%%%%%%%%%%%%C2%%%%%%############***************A2***************@@@@@@@@@@@@@@@@@@像上⾯给出的那样，A1到A2可能是⼀个循环，C1到C2可能是⼀个循环。
2.while,for,repeat,等循环结构和if,then,else条件结构与Pascal中相同。
（for循环有⼀点不同）。
4.多重赋值i←j←e是将表达式e的值赋给变量i和j；等价于赋值j←e，再进⾏i←j。
5.变量在没有显⽰说明的情况下，⼀般不使⽤全局变量。
6.数组元素是通过“数组名[下标]”，这样的形式来访问的。
7.参数采⽤按值传递的⽅式。
8.布尔运算"&&"(C语⾔版)和"||"(C语⾔版)有短路能⼒，如下所⽰：if(a>b&&a%2==0)//词语句中，如果a>b不成⽴，则不会再次判断a%2==0if(a>b||a%2==0)//词语句中，如果a>b成⽴，则不会再次判断a%2==09.复合数据⼀般组织成对象，它们是由"属性"或"域"组成的。
域的访问是由域名后跟由⽅括号括住的对象名形式来表⽰。
（坚持）Never Give Up !。
用伪代码描述算法
快速排序算法是一种常见的、非常高效的排序算法，它的基本思想是：通过不断比较
待排序的数据，将数据分成两个子集，左边子集的所有数据的值比选定的“中间元素”的
值小，右边子集的数据的值比它大。
然后继续分割两个子集，直到所有数据都有序。
基本步骤：
（1）从待排序的数据中选出一个“中介”元素，并把数据分成两个子集。
（2）根据比中介元素大或小的不同，把当前子集划分为两个子子集。
（3）重复上述步骤，直到数据分组是每组只有一个元素（即每一组只有一个元素为止）。
（4）把所有子集和子子集按照步骤1-3的顺序重新组合，在组合的过程中保证子集
左边的元素比中间元素小，子集右边的元素比中介元素大。
（5）对子集和子子集再次重复步骤1-3，直到只剩下一个集合，即所有的数据都有序为止。
其主要思想是：将待排序的数据按照中间元素分成两组，其中一组的元素都比中介元
素小，另一组的元素都比中介元素大，然后再进行分割，直到每组都只剩下一个元素为止，这样就对所有数据都排序了。
目录算法概论 (1)序言 (1)第一章 (2)乘法 (2)除法 (2)两数的最大公因数 (2)扩展 (2)RSA (3)第二章：分治算法 (3)整数相乘的分治算法 (3)递推式 (3)2.3合并排序 (3)第三章图的分解 (4)3.2.1寻找从给定顶点出发的所有可达顶点 (4)3.2.2 深度优先搜索 (4)第四章 (4)4.2、广度优先搜索 (4)4.4.1、dijkstra最短路径算法 (5)4.6.1、含有负边 (5)Bellman-Ford算法 (6)4.7、有向无环图的最短路径 (6)第五章贪心算法 (6)5.1 最小生成树 (6)算法概论序言Fibonacci数列：死板的算法：function Fib1(n)If n=0:return 0If n=1:return 1Return fib1(n-1)+fib1(n-2)(递归，很多计算是重复的，不必要)合理的算法：functionFib2(n)If n=0:return 0Create an array f[0…n]f[0]=0,f[1]=1fori=2…n:f[i]=f[i-1] + f[i-2]return f[n](随时存储中间计算结果，之后直接调用)大O符号：若存在常数c>0，使得f(n)<=c*g(n)成立，则f=O(g)。
f增长的速度慢于g。
第一章乘法：functionMultiply(x,y)If y=0:return 0z=multiply(x,y/2)//向下取整If y is even: //even---偶数return 2zelse:return x+2z除法：functionDivide(x,y)If x=0: return (q,r)=(0,0)(q,r)=divide( x/2 ,y) //向下取整q=2*q,r=2*rif x is odd:r=r+1if r>=y :r=r-y,q=q+1return (q,r)p22两数的最大公因数：function Euclid(a,b)if b=0: return areturn Euclid(b,a mod b)扩展：function extended-Euclide(a,b)if b=0: return (1,0,a)(x1,y1,d)=extended-Euclide(b,a mod b)retrun (y1,x1-a/b*y1,d)RSA:(X^e)^d ==X mod Nd=e^-1 mod(p-1)(q-1)N=pq第二章：分治算法整数相乘的分治算法：function multiply(x,y)input:n-bit positive integers x and youtput:their productif n=1:return xyxl,xr=leftmost n/2_^ ,rightmost n/2_v bits of x // _^表示向上取整，_v表示向下取整yl,yr=leftmost n/2_^ ,rightmost n/2_v bits of yp1=multiply(xl,yl)p2=multiply(xr,yr)p3=multiply(xl+xr,yl+yr)return p1*p2+(p3-p1-p2)*2^(n/2)+p22.2递推式：T(n)={ O(nd):d>logba|| O(n d *log n) :d=log b a|| O(n^(log b a)): d<log b a}2.3合并排序function mergersort(a[1…n])if n>1:return merge(mergesort( a[1…n/2]), a[n/2+1…n]))else:return afunction merge(x[1…k], y[1…L] )if k=0: return y[1…L]if L=0: return x[1…k]if x[1]<=y[1]:return x[1]＆merge(x[2…k],y[1…L])else:return y[1]&merge( x[1…k], y[2…L] )第三章图的分解3.2.1寻找从给定顶点出发的所有可达顶点：procedure explore(G,v)input:G=(V,E) is a graph; v ∈Voutput:visited(u) is set to true for all nodes u reachable from vvisited(v)=trueprevisit(v)for each edge(v,u)∈E:if not visited(u):explore(u)postvisit(v)3.2.2 深度优先搜索：proceduredfs(G)for all v ∈V:visited(v)=falsefor all v∈V:if not visited(v):explore(v)线性化序列：对图深度优先搜索，取post的降序序列。
求强连通部件：1、在反转图上运行深度优先搜索，得到post值大的点v，运行explore(G,v)。
第四章：4.2、广度优先搜索bfs(G,s)算法简述：所有dist(u)设为无穷大；dist(s)=0;入队Q(s);while Q 不空：出队u：所有边u->v:if dist(v)=∞：入队v,dist(v)=dist(u)+1--------------procedurebfs(G,s)for all u∈V:dist(u)=∞dist(s)=0Q=[s] (queue containing just s,入队s,以dist值为key )while Q is not empty:u=eject(Q) //出队最小的keyfor all edges(u,v)∈E∶ifdist(v)=∞:inject(Q,v)dist(v)=dist(u)+14.4.1、dijkstra最短路径算法：（只适用于权值为正值）proceduredijkstra(G,l,s)input:Graph G=(V,E), directed or undirectedOutput:For all vertices u reachable from s,dist(u) is set to the distance from s to u.For all u∈V:Dist(u)=∞Prev(u)=nildist(s)=0H=makequeue(V) (using dist-values as keys)while H is not empty:u=deletemin(H)for all edges(u,v)∈E:ifdist(v)>dist(u)+l(u,v):dist(v)=dist(u)+l(u,v)prev(v)=udecreasekey(H,v) //更新队列4.6.1、含有负边：procedure update((u,v)∈E)dist(v)=min{ dist(v), dist(u)+l(u,v) }Bellman-Ford算法：procedure shortest-paths(G,l,s)for all u∈V:Dist(u)=∞Prev(u)=nildist(s)=0repeat |V|-1 times:for all e∈E:update(e)4.7、有向无环图的最短路径procedure dag-shortest-paths(G,l,s)for all u∈V:Dist(u)=∞Prev(u)=nildist(s)=0Linearize G //线性化for each u∈V,in linearized order:for all edges (u,v)∈E:update(u,v)第五章贪心算法5.1 最小生成树Kruskal:不断重复地选择未被选中的边中权重最轻且不会开成环的一条。
子函数：proceduremakeset(x)π(x)=x //π(x)意为x的父节点rank(x)=0function find(x) //找x的根节点while x≠π(x): x=π(x)return x或：function find(x)if x≠π(x): π(x)=find(π(x))returnπ(x)procedure union(x,y)rx=find(x)ry=find(y)ifrx=ry:returnif rank(rx)>rank(ry):π(ry)=rxelse:π(rx)=ryif rank(rx)=rank(ry):rank(ry)=rank(ry)+1Kruskal:procedurekruskal (G,w)for all u∈V:makeset (u)X={}sort the edges E by weightfor all edges {u,v}∈E ,in increasing order of weight:if find(u)≠find(v):add edge {u,v} to Xunion(u,v)prim算法：procedure prim(G,w)for all u∈V:cost(u)=∞prev(u)=nilpick any initial node u0cost(u0)=0H=makequeue(V) (priority queue,using cost-values as keys) while H is not empty:v=deletemin(H)for each {v,z}∈E:if cost(z)>w(v,z):cost(z)=w(v,z)prev(z)=vdecrease(H) //更新。
