Question

计算机网络的最短路径算法有哪些？对应哪些协议？

Answer 1

　　用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：
　　Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要介绍其中的三种。

　　最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
　　算法具体的形式包括：

　　确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

　　确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
　　确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

　　全局最短路径问题：求图中所有的最短路径。
　　Floyd

　　求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。

　　Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。
　　Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。

　　Floyd-Warshall的原理是动态规划：

　　设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

　　若最短路径经过点k，则Di,j,k = Di,k,k-1 + Dk,j,k-1；

　　若最短路径不经过点k，则Di,j,k = Di,j,k-1。

　　因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

　　在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

　　Floyd-Warshall算法的描述如下：

　　for k ← 1 to n do

　　for i ← 1 to n do

　　for j ← 1 to n do

　　if (Di,k + Dk,j < Di,j) then

　　Di,j ← Di,k + Dk,j;

　　其中Di,j表示由点i到点j的代价，当Di,j为 ∞ 表示两点之间没有任何连接。

　　Dijkstra

　　求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）,可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。
　　源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。

　　当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2） 。可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。
　　Bellman-Ford

　　求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。

　　Bellman-Ford算法是求解单源最短路径问题的一种算法。

　　单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。

　　与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环

　　路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。
　　SPFA

　　是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k< 与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。
　　SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的。

　　与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。
　　在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。
　　SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA。

Answer 2

Bellman-Ford算法，对应距离矢量路由协议RIP

Answer 3

Dijkstra算法，A*算法和D*算法等 开放最短路径优先(OSPF)_网络协议

参http://zhidao.baidu.com/question/155864296.html
http://blog.chinaunix.net/uid-27164517-id-3287891.html
http://www.bitscn.com/network/protocol/200604/14786.html

Answer 4

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为止