03
Floyd算法
Floyd它可以方便地求出任意两点间的距离，求的是多源最短路径。最大的优点就是容易理解和编写，算法的核心代码只有5行：
//核心代码 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dist[i][k]+dist[k][j]<dist[i][j]) dist[i][j]=dist[i][k]+dist[k][j];
但看了代码后童鞋们会发现，Floyd算法的时间复杂度比较高(n^3)，不适合计算大量数据。
我们可以把Floyd算法理解为“如果两点间的路径长度，大于这两点通通过第三点连接的路径长度，那么就修正这两点的最短路径”。
下面我们来具体讲解一下算法的思路：
在代码中，i，j表示的是我们当前循环中所求的起点、终点。k则是我们引入的“中转点”。为什么要引入中转点呢？因为当我们寻找i、j之间的最短路径时，要么是i、j间的距离，要么就是经过其他点中转：i→k→。。。→j。
为了方便讲解，我们给出一个概念“松弛”：如果dist【i】【j】>dist【i】【k】+dist【k】【j】（e表示两点间的距离），我们把dist【i】【j】更新为dist【i】【k】+dist【k】【j】，达到“经过中转点k后距离缩短，并记录”的目的。
在第1轮循环中，我们以1为中转点，把任意两条边的距离松弛一遍，更新数组数据。
在第2轮循环中，我们以2为中转点，再松弛一遍。这时，对第1轮松弛更新过的数据，如果继续更新，相当于中转到1，2后取得当前最短路径。
。。。。。。
最后得到的数组就是任意两点间的最短路径。
这个时候再看一遍这句话：“如果两点间的路径长度，大于这两点通通过第三点连接的路长度，那么就修正这两点的最短路径。”是不是就能够理解了？
下面放码。
//Floyd算法解最短路径问题 #include <iostream> using namespace std; const int INF=99999; int main() { //读入数据的过程和dfs没什么区别，就不讲解了 int i,j,n,m,k,a,b,c; int dist[105][105]; cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) dist[i][j]=0; else dist[i][j]=INF; for(i=1;i<=m;i++) { cin>>a>>b>>c; dist[a][b]=c; } //核心代码 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(dist[i][k]+dist[k][j]<dist[i][j]) dist[i][j]=dist[i][k]+dist[k][j]; for (i=1;i<=n;i++){ for(j=1;j<=n;j++){ cout<<dist[i][j]<<"\t"; } cout<<endl; } return 0; }
04
Dijkstra算法
Dijkstra 算法主要解决的是单源最短路径问题。它的时间复杂度一般是o(n^2) ，因此相对于Floyd算法速度上有极大的优势，可以处理更多的数据。
算法的核心依旧是上文讲到的“松弛”。只不过松弛的方式略有不同：它通过不断选择距离起点最近的顶点作为新的起点，再利用这些新的起点来松弛其他较远的点，最终计算出所有点到起点最短路径。
这样听起来有点绕，我们基于代码，通过例子来讲解。
我们把点i到起点1的距离定义为dis【i】（现在知道我上面为什么用dist了吧！），用一个book来标记该点是否已经为最短状况，初始化为0（否）
核心代码分为两部分：第一部分判断最小，第二部分进行松弛。
以原题为例：
第一次循环，我们先进入第一部分判断较短距离。第一次到起点1只有2号，5号点有最短距离，分别为2，10。
下一步，我们找到2，5号中到起点1距离较短的点u（这里是2号）。
进入第二部分松弛。对点v，如果v到起点1的距离大于u（即2）到1的距离加上2到v的距离，更新v到原点的距离dis【v】。
开始循环。
在下一次循环中，相当于把点2当作新的起点代替点1，进行上述操作。
可以看出，Dijkstra是一种基于贪心策略的算法，也是一种以DFS为思路的算法。
#贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，贪心算法所做出的是在某种意义上的局部最优解。#
为什么下一条次较短路径要这样选择？（贪心准则的正确性）
因为我们算的是到起点的距离，所以所有路径必然要经过与起点最近的2（或不经过任何别的中转点），而相对于2点，5号点距离更远，还有通过2点松弛之后缩短路径的可能性，所以我们直接选择2为新的起点进行下一步松弛。那么，第k次循环就表示松弛了k次，即经过了k-1个中转点（或k-1条边）才到达起点1，留在dis（）数组中的距离就是经过中转点个数<=k-1（可能无需经过这么多个点就达到）的最短路径。
Dijkstra算法主要特点是以起始点为中心向外层层扩展，从一个顶点到其余各顶点的最短路径算法，直到扩展到最远点（指经过的中转点最多，）为止。（这里就是类似BFS的地方）
选择最短路径顶点的时候依照的是实现定义好的贪心准则，所以该算法也是贪心算法的一种。
还有说法是Dijkstra也属于动态规划。这里我就不发表言论了，因为本小白还不懂(┬＿┬)。
下面给出代码。
//Dijkstra算法解最短路径问题 #include<iostream> using namespace std; const int INF=99999; int main() { int dist[105][105] ; int dis[105] ; int book[105] ; int i,j,n,m,a,b,c,u,v,Min; cin>>n>>m; //开始了！！！ for(i = 1;i <= n;i++) //每轮循环计算的是中转点为n-1时的最小点。 for(j = 1;j <= n;j++) if(i == j) dist[i][j] = 0; else dist[i][j] = INF; for(i = 1;i <= m;i++) { cin>>a>>b>>c; dist[a][b] = c; } for(i = 1;i <= n;i++) dis[i] = dist[1][i]; for(i = 1;i<=n;i++) //初始化标记book book[i] = 0; book[1] = 1; for(i = 1;i <= n-1;i++) //筛出当前没有访问的并且与上一点直接相连的距离最小的点。 { Min = INF; for(j = 1;j <= n;j++) { if(book[j] == 0&& dis[j] < Min) { Min = dis[j]; u = j; } } book[u] = 1; for(v = 1;v <= n;v++) //松弛 { if(dist[u][v] < INF) { if(dis[v] > dis[u] + dist[u][v]) dis[v] = dis[u] + dist[u][v]; } } } for(i = 1;i <= n;i++) cout<<dis[i]<<"\t"; return 0; }
