求图的多源最短路的算法

① 弗洛伊德算法求出最短距离

（1）利用二维数组dist[i][j]记录当前vi到vj的最短路径长度，数组dist的初值等于图的带权邻接矩阵;

（3）依次向S中加入v0,v1…vn-1，每加入一个顶点，对dist[i][j]进行一次修正：设S={v0,v1…vk-1}，加入vk，则dist(k)[i][j]=min{dist(k-1)[i][j]，dist(k-1)[i][k]+dist(k-1)[k][j]}。

dist(k)[i][j]的含义：允许中间顶点的序号最大为k时从vi到vj的最短路径长度。
dist(n-1)[i][j]就是vi到vj的最短路径长度。

弗洛伊德最短距离算法（FloydShortestPathAlgorithm）又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
中文名弗洛伊德最短距离算法
外文名FloydShortestPathAlgorithm
所属学科IT
所属领域程序设计
简介
最短路问题是网络最优化中一个基本而又非常重要的问题，这一问题相对比较简单，在实际生产和生活中经常遇到，许多的网络最优化问题可以化为最短路问题，或者用最短路算法作为其子程序.因此，最短路的用途已远远超出其表面意义迄今为止，所有最短路算法都只对不含负回路的网络有效，实际上对含有负回路的网络，其最短路问题是NP困难的，因此本研究所讨论的网络也不含负回路.此外，如果将无向图每条边用两条端点相同、方向相反的弧来代替，可以将其化为有向图，因而不讨论无向图.本研究中未述及的术语、记号。
Floyd算法是一种用于寻找给定加权图中顶点间最短路径的算法，以1978年图灵奖获得者斯坦福大学计算机科学系教授RobertW．Floyd命名。Floyd算法采用动态规划的原理计算两两顶点间最短路径，主要解决网络路由寻找最优路径的问题。

② 数学最短路径问题最方便的解法是什么

用于解决最短路径问题的算法被称做“最短路径算法” ，有时被简称作“路径算法” 。最常用 的路径算法有： 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 算法的描述如下： 1.for k ← 1 to n do 2.for i ← 1 to n do 3.for j ← 1 to n do 4.if (Di,k + Dk,j<Di,j) then 5.Di,j ← Di,k + Dk,j; 其中 Di,j 表示由点 i 到点 j 的代价，当 Di,j 为∞表示两点之间没有任何连接。 Dijkstra 求单源、无负权的最短路。时效性较好，时间复杂度为 O（V*V+E） 。 源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV） 。 当是稀疏图的情况时，此时 E=V*V/lgV，所以算法的时间复杂度可为 O（V^2） 。若是斐波那 契堆作优先队列的话，算法时间复杂度，则为 O（V*lgV + E） 。 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<<V） 。 。 与 Bellman-ford 算法类似， SPFA 算法采用一系列的松弛操作以得到从某一个节点出发到达图 中其它所有节点的最短路径。所不同的是，SPFA 算法通过维护一个队列，使得一个节点的 当前最短路径被更新之后没有必要立刻去更新其他的节点， 从而大大减少了重复的操作次数。 SPFA 算法可以用于存在负数边权的图，这与 dijkstra 算法是不同的。 与 Dijkstra 算法与 Bellman-ford 算法都不同，SPFA 的算法时间效率是不稳定的，即它对于不 同的图所需要的时间有很大的差别。 在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度 仅为 O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为 Bellman-ford 算法，其时间复杂度为 O(VE)。 SPFA 算法在负边权图上可以完全取代 Bellman-ford 算法， 另外在稀疏图中也表现良好。 但是 在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的 Dijkstra 算法，以及 它的使用堆优化的版本。通常的 SPFA 算法在一类网格图中的表现不尽如人意。 

③ 关于Floyd算法，path数组一定能保存正确的路径吗

你说的是浙大的mooc数据结构，我也看了，她漏了path的一步初始化，即如果存在直接边的情况下(D[i][j]<INFINITY)，是需要把path[i][j]初始化为i的。
因为如果i和j直接边是它们的最短路径，
if (Dist[i][k] + Dist[k][j] < Dist[i][j]) {
Dist[i][j] = Dist[i][k] + Dist[k][j];
Path[i][j] = k;
}
是不会更新path的，这样直接边作为最短路径的path会为-1.