求解：图论中常见的最短路径算法有几种？都是什么？

算法 Algorithm

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是 *** 作实现的算法。

一个算法应该具有以下五个重要的特征：

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随机化算法

在图论基础上研究网络一般规律和网络流问题各种优化理论和方法的学科，是运筹学的一个分支。网络是用节点和边联结构成的图，表示研究诸对象及其相互关系，如铁路网、电力网和通信网等。

中文名

网络理论

外文名

net theory

提出者

Georg Simmel

国家

德国

关键字

网络流、优化理论

快速

导航

发展概况

最大流量问题

最短路径问题

最短树问题

最小费用流

简介

在图论基础上研究网络一般规律和网络流问题各种优化理论和方法的学科，是运筹学的一个分支。网络是用节点和边联结构成的图，表示研究诸对象及其相互关系，如铁路网、电力网和通信网等。网络中的节点代表任何一种流动的起点、运转点和终点（如车站、港口、城镇、计算机终端和工程项目的事件等）。网络中的边代表任何物流、能流或信息流通过的通道（如输电线、通信线、铁路线和各事件之间的次序等）。在网络中每条边上赋予某个正数，称为该边的权，它可以表示路程、流量、时间和费用等。建立网络的目的都在于把某种规定的物质、能量或信息从某个供应点最优地输送到另一个需求点去。例如，在管道网络中要以最短的距离、最大的流量和最小的费用把水、石油或天然气从供应点送到用户那里。

网络理论

网络理论

发展概况

网络理论起源于图论[1] 。1845年GR基尔霍夫应用图论和[2] 矩阵理论证明了电网络中两个重要定律，即基尔霍夫电流定律和电压定律，不仅为图论的发展作出了贡献，也奠定了网络理论的基础。20世纪50年代以来，随着网络理论的广泛应用，许多学者提出优化计算的方法。1956年LR小福特和DR富尔克森提出寻找最大流量的标号算法。1959年EW戴克斯特拉提出寻找最短路径的标号算法。1961年，富尔克森提出求解更一般的最小费用流的状态算法，这是解最短路径、最大流量与最小费用流的统一方法，是网络理论中最基本的结果之一。此后又相继提出了各种类型的网络流问题，诸如带下界容量的网络流、动态流、带增益的流和多种物资流等问题，并得到一系列结果。

网络理论

网络理论

最大流量问题

当物质流或信息流通过给定的网络时（图1）,在流过每条边的流量xij不超过该边允许通过的流量cij的条件下,求出从发点s向收点t输出的最大流量f，即在满足的条件下,使f最大。最大流量问题是一个特殊的线性规划问题，有许多求解方法。一种有效的计算方法是福特-富尔克森法，它是根据最大流量-最小割集原理，通过标号算法，求出在上述约束条件下从发点s到收点t的最大流量f 的数值。其计算步骤如下：①绘制一个能满足上述约束条件的网络可行流（图2）。边上的数字为允许流量cij，括号内的数字为给定的可行流。②找出一条增广链。增广链是指从发点s到收点t的链中，满足正向边上xij<cij和反向边上xji>0的链。图2中用粗线表示的{vs，v2,v3,v4,v6,vt} 是一条增广链。其中v2,v3为反向边,其余均为正向边。③调整可行流,即在增广链的各边上，属正向边加上一个修正量ε，属反向边减去一个修正量ε，即xij+εj，xji-εj。

网络理论

网络理论

最短路径问题

一般提法是：寻找网络中两点间的最短路径,即寻找连接这两点的边的总权数(可以是距离、时间、费用等)为最小的通路。图4为最短路径问题的一个例子。最短路径问题有两种算法。戴克斯特拉法　1959年提出。其计算方法是：从始点vs,标以零值,并记在vs旁的方括号内。然后依节点序号顺序找出到达各点的最短距离,并说明来自何方,例如在节点v3处标上v2,4,即表示来自节点v2，距离累计为4。戴克斯特拉法可以通过编制计算程序,在计算机上运算。

图论图的表示：邻接矩阵，邻接表，边表

传递闭包和floyd

最小生成树算法(至少会一种)

单源最短路dijkstra（O(n2)）或者bellman（spfa优化，O(km)）

拓扑排序

树 树的先序、中序、后序遍历

树中的最长路（两遍bfs或者dfs）

并查集

有能力的话：

Dijkstra算法的堆优化、求割点、求割边、强连通分量、欧拉路（边一次）、汉密尔顿回路（点一次）、差分约束系统

匹配算法（最大匹配，最小点覆盖，最小路径覆盖，最大独立集)

网络流算法（最大流dinic，最小费用流spfa）

动态规划动态规划的优化（快速幂，改变状态，优化转移，单调性，四边形不等式）

归并树(逆序对)平衡树（sbt、treap、splay）后缀数组

必须知识：最短路径问题

1Dijkstra

适用于满足所有权系数大于等于0（lij≥0）的网络最短路问题，能求出起点v1到所有其他点vj的最短距离；

朴素的Dijkstra算法复杂度为O(N^2)，堆实现的Dijkstra复杂度为O(NlogN)

2bellman-ford

适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点v1到所有其它点 vj的最短距离。bellman-ford算法复杂度为O(VE)。

3Floyed

适用于有负权系数，可以求出图上任意两点之间的最短路径。DP思想的算法，时间复杂度为O(N^3);

for ( k= 1; k<= n; k++)

for ( i= 1; i<= n; i++)

if (graph[i][k]!=INF)

for ( j= 1; j<= n; j++)

if (graph[k][j]!=INF && graph[i][k]+graph[k][j]< graph[i][j])

graph[i][j]= graph[i][k]+ graph[k][j];

NO1 s-t最大流

两大类算法

1增广路算法

Ford-Fulkerson算法: 残留网络中寻找增加路径

STEP0：置初始可行流。

STEP1：构造原网络的残量网络，在残量网络中找s－t有向路。如果没有，算法得到最大流结束。否则继续下一步。

STEP2：依据残量网络中的s－t有向路写出对应到原网络中的s－t增广路。对于增广路中的前向弧，置s(e)＝u(e)- f(e)。对于反向弧，置s(e)＝f（e） STEP3：计算crement=min{s（e1），s（e2），…，s（ek）}

STEP4：对于增广路中的前向弧，令f(e)＝f(e)＋crement；对于其中的反向弧，令f(e)＝f(e)-crement，转STEP1。

关键点:寻找可增广路。决定了算法复杂度。

实现：Edmonds-Karp 通过采用了广度优先的搜索策略得以使其复杂度达到O(VE^2)。

优化—> Dinic算法()

Dinic算法的思想是为了减少增广次数，建立一个辅助网络L，L与原网络G具有相同的节点数，但边上的容量有所不同，在L上进行增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流。分层的目的是降低寻找增广路的代价。

算法的时间复杂度为O(V^2E)。其中m为弧的数目，是多项式算法。邻接表表示图，空间复杂度为O(V+E)。

2预流推进算法

一般性的push-relabel算法: 时间复杂度达到O(V^2E)。()

relabel-to-front算法->改进

最高标号预流推进:时间复杂度O(V^2sqrt(E))

NO2 最小费用最大流

求解最小费用流的步骤和求最大流的步骤几乎完全一致，只是在步骤1时选一条非饱和路时，应选代价和最小的路，即最短路。

步骤1 选定一条总的单位费用最小的路，即要给定最小费用的初始可行流，而不是包含边数最小的路。

步骤2 不断重复求最大流的步骤来进行，直到没有饱和路存在为止。然后计算每个路的总费用。

和Edmonds-Karp标号算法几乎一样，因为这两种算法都使用宽度优先搜索来来寻找增广路径，所以复杂度也相同，都是O(VE^2)。

连续最短路算法 + 线性规划对偶性优化的原始对偶算法()

传说中，没见过，据说复杂度是O(V^3)

NO3 有上下届的最大流和最小流（通过添加点来进行转化）()

NO4 相关图论算法

二分图最大匹配： 加s和t构造最大流

专用算法：hungary算法 O(MN)

二分图最佳匹配： 加s和t构造最小费用最大流

专用算法：KM算法

朴素的实现方法,时间复杂度为O(n^4)

加上松弛函数O(n^3)

最小路径覆盖：

顶点数－二分图的最大匹配

s-t最小边割集：

最大流最小割定理：最小割等于最大流

普通最小边割集：

Stoer-Wagner Minimum Cut O(n^3)

二分图的最大独立集：

N - 二分图的最大匹配（POJ monthly）girls and boys

反证法证明

普通图的最大独立集是np问题。()

随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。一个数图谜题包含一个空白的方格，以及在表格每一行右侧、每一列下方的一组线索数。每组都有一个或多个数字，这些数字就是解题的线索。

图论的应用领域有很多。凡是涉及排列组合优化问题的都免不了要用到图论中的各种知识。比如通信编解码，矩阵运算，任务分配，GPS路径规划等等。

至于图论的经典著作，可以自己去google一下graph theory。

1 最短路问题（SPP－shortest path problem）

一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。

2 公路连接问题

某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？

3 指派问题（assignment problem）

一家公司经理准备安排 名员工去完成 项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？

4 中国邮递员问题（CPP－chinese postman problem）

一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。

5 旅行商问题（TSP－traveling salesman problem）

一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。

6 运输问题（transportation problem）

某种原材料有 个产地，现在需要将原材料从产地运往 个使用这些原材料的工厂。假定 个产地的产量和 家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？

7最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法

8计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的 *** 作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(n^3)。第二种解决这一问题的方法是由Floyd R W提出的算法，称之为Floyd算法。(可以解决第一个问题)

9prim算法、Kruskal算法构造最小生成树（使所有点连通）

10匈牙利算法、Kuhn-Munkres算法解决人员分配问题

11Euler回路的Fleury算法（中国邮递员问题）

12最大流的一种算法—标号法（用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。）

我的计算机不好，用的是MATLAB，网上很多资料可以百度到。程序好直接百度对应算法搞成C的吧……

算法很多百度能到……