1、最短路径问题介绍
问题解释：
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径
解决问题的算法：
之前已经对Dijkstra算法做了介绍（不懂的可以看这篇博客：Dijkstra算法详解），所以这篇博客打算对Floyd算法做详细的的介绍。
2、Floyd算法的介绍
通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入两个矩阵，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。矩阵P中的元素b[i][j]，表示顶点i到顶点j经过了b[i][j]记录的值所表示的顶点。
假设图G中顶点个数为N，则需要对矩阵D和矩阵P进行N次更新。初始时，矩阵D中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞，矩阵P的值为顶点b[i][j]的j的值。 接下来开始，对矩阵D进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k-1]+a[k-1][j]”，则更新a[i][j]为”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后，操作完成！
3、Floyd算法的实例过程
上面，我们已经介绍了算法的思路，如果，你觉得还是不理解，那么通过一个实际的例子，把算法的过程过一遍，你就明白了，如下图，我们求下图的每个点对之间的最短路径的过程如下：
第一步，我们先初始化两个矩阵，得到下图两个矩阵：
、
第二步，以v1为中阶，更新两个矩阵：
发现，a[1][0]+a[0][6] < a[1][6] 和a[6][0]+a[0][1] < a[6][1]，所以我们只需要矩阵D和矩阵P，结果如下：
通过矩阵P，我发现v2–v7的最短路径是：v2–v1–v7
第三步：以v2作为中介，来更新我们的两个矩阵，使用同样的原理，扫描整个矩阵，得到如下图的结果：
OK，到这里我们也就应该明白Floyd算法是如何工作的了，他每次都会选择一个中介点，然后，遍历整个矩阵，查找需要更新的值，下面还剩下五步，就不继续演示下去了，理解了方法，我们就可以写代码了。
Floyd算法
1.定义概览
Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
2.算法描述
1)算法思想原理：
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
2).算法描述：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
3).Floyd算法过程矩阵的计算----十字交叉法
方法：两条线，从左上角开始计算一直到右下角 如下所示
给出矩阵，其中矩阵A是邻接矩阵，而矩阵Path记录u,v两点之间最短路径所必须经过的点
typedef struct
{
char vertex[VertexNum]; //顶点表
int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表
int n,e; //图中当前的顶点数和边数
}MGraph;
void Floyd(MGraph g)
{
int A[MAXV][MAXV];
int path[MAXV][MAXV];
int i,j,k,n=g.n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
}
算法时间复杂度:O(n3)
对上面代码还可以进一步优化？答案是肯定的，不信你看下面这个小故事告诉你诀窍：
暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。
上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。这个问题这也被称为“多源最短路径”问题。
现在需要一个数据结构来存储图的信息，我们仍然可以用一个4*4的矩阵（二维数组e）来存储。比如1号城市到2号城市的路程为2，则设e[1][2]的值为2。2号城市无法到达4号城市，则设置e[2][4]的值为∞。另外此处约定一个城市自己是到自己的也是0，例如e[1][1]为0，具体如下。
现在回到问题：如何求任意两点之间最短路径呢？通过之前的学习我们知道通过深度或广度优先搜索可以求出两点之间的最短路径。所以进行n2遍深度或广度优先搜索，即对每两个点都进行一次深度或广度优先搜索，便可以求得任意两点之间的最短路径。可是还有没有别的方法呢？
我们来想一想，根据我们以往的经验，如果要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点k），并通过这个顶点k中转即a->k->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转的顶点k是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多点中转会更短，即a->k1->k2b->或者a->k1->k2…->k->i…->b。比如上图中从4号城市到3号城市（4->3）的路程e[4][3]原本是12。如果只通过1号城市中转（4->1->3），路程将缩短为11（e[4][1]+e[1][3]=5+6=11）。其实1号城市到3号城市也可以通过2号城市中转，使得1号到3号城市的路程缩短为5（e[1][2]+e[2][3]=2+3=5）。所以如果同时经过1号和2号两个城市中转的话，从4号城市到3号城市的路程会进一步缩短为10。通过这个的例子，我们发现每个顶点都有可能使得另外两个顶点之间的路程变短。好，下面我们将这个问题一般化。
当任意两点之间不允许经过第三个点时，这些城市之间最短路程就是初始路程，如下。
如现在只允许经过1号顶点，求任意两点之间的最短路程，应该如何求呢？只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。其中i是1~n循环，j也是1~n循环，代码实现如下。
1 for(i=1;i<=n;i++)
2 {
3 for(j=1;j<=n;j++)
4 {
5 if ( e[i][j] > e[i][1]+e[1][j] )
6 e[i][j] = e[i][1]+e[1][j];
7 }
8 }
在只允许经过1号顶点的情况下，任意两点之间的最短路程更新为：
通过上图我们发现：在只通过1号顶点中转的情况下，3号顶点到2号顶点（e[3][2]）、4号顶点到2号顶点（e[4][2]）以及4号顶点到3号顶点（e[4][3]）的路程都变短了。
接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小，代码实现为如下。
1 //经过1号顶点
2 for(i=1;i<=n;i++)
3 for(j=1;j<=n;j++)
4 if (e[i][j] > e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j];
5 //经过2号顶点
6 for(i=1;i<=n;i++)
7 for(j=1;j<=n;j++)
8 if (e[i][j] > e[i][2]+e[2][j]) e[i][j]=e[i][2]+e[2][j];
在只允许经过1和2号顶点的情况下，任意两点之间的最短路程更新为：
通过上图得知，在相比只允许通过1号顶点进行中转的情况下，这里允许通过1和2号顶点进行中转，使得e[1][3]和e[4][3]的路程变得更短了。
同理，继续在只允许经过1、2和3号顶点进行中转的情况下，求任意两点之间的最短路程。任意两点之间的最短路程更新为：
最后允许通过所有顶点作为中转，任意两点之间最终的最短路程为：
整个算法过程虽然说起来很麻烦，但是代码实现却非常简单，核心代码只有五行：
1 for(k=1;k<=n;k++)
2 for(i=1;i<=n;i++)
3 for(j=1;j<=n;j++)
4 if(e[i][j]>e[i][k]+e[k][j])
5 e[i][j]=e[i][k]+e[k][j];
这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。其实这是一种“动态规划”的思想！
动态转移方程：dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]);
下面给出这个算法的完整代码：
1 #include <stdio.h>
2 int main()
3 {
4 int e[10][10],k,i,j,n,m,t1,t2,t3;
5 int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
6 //读入n和m，n表示顶点个数，m表示边的条数
7 scanf("%d %d",&n,&m);
8
9 //初始化
10 for(i=1;i<=n;i++)
11 for(j=1;j<=n;j++)
12 if(i==j) e[i][j]=0;
13 else e[i][j]=inf;
14 //读入边
15 for(i=1;i<=m;i++)
16 {
17 scanf("%d %d %d",&t1,&t2,&t3);
18 e[t1][t2]=t3;
19 }
20
21 //Floyd-Warshall算法核心语句
22 for(k=1;k<=n;k++)
23 for(i=1;i<=n;i++)
24 for(j=1;j<=n;j++)
25 if(e[i][j]>e[i][k]+e[k][j] )
26 e[i][j]=e[i][k]+e[k][j];
27
28 //输出最终的结果
29 for(i=1;i<=n;i++)
30 {
31 for(j=1;j<=n;j++)
32 {
33 printf("%10d",e[i][j]);
34 }
35 printf("\n");
36 }
37
38 return 0;
39 }
有一点需要注意的是：如何表示正无穷。我们通常将正无穷定义为99999999，因为这样即使两个正无穷相加，其和仍然不超过int类型的范围（C语言int类型可以存储的最大正整数是2147483647）。在实际应用中最好估计一下最短路径的上限，只需要设置比它大一点既可以。例如有100条边，每条边不超过100的话，只需将正无穷设置为10001即可。如果你认为正无穷和其它值相加得到一个大于正无穷的数是不被允许的话，我们只需在比较的时候加两个判断条件就可以了，请注意下面代码中带有下划线的语句。
1 //Floyd-Warshall算法核心语句
2 for(k=1;k<=n;k++)
3 for(i=1;i<=n;i++)
4 for(j=1;j<=n;j++)
5 if(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])
6 e[i][j]=e[i][k]+e[k][j];
上面代码的输入数据样式为：
1 4 8
2 1 2 2
3 1 3 6
4 1 4 4
5 2 3 3
6 3 1 7
7 3 4 1
8 4 1 5
9 4 3 12
第一行两个数为n和m，n表示顶点个数，m表示边的条数。
接下来m行，每一行有三个数t1、t2 和t3，表示顶点t1到顶点t2的路程是t3。
得到最终结果如下：
通过这种方法我们可以求出任意两个点之间最短路径。它的时间复杂度是O(N3)。令人很震撼的是它竟然只有五行代码，实现起来非常容易。正是因为它实现起来非常容易，如果时间复杂度要求不高，使用Floyd-Warshall来求指定两点之间的最短路或者指定一个点到其余各个顶点的最短路径也是可行的。当然也有更快的算法，请看下一节：Dijkstra算法。
另外需要注意的是：Floyd-Warshall算法不能解决带有“负权回路”（或者叫“负权环”）的图，因为带有“负权回路”的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->…->1->2->3这样路径中，每绕一次1->-2>3这样的环，最短路就会减少1，永远找不到最短路。其实如果一个图中带有“负权回路”那么这个图则没有最短路。
正如我们所知道的，Floyd算法用于求最短路径。Floyd算法可以说是Warshall算法的扩展，三个for循环就可以解决问题，所以它的时间复杂度为O(n^3)。
Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。
很简单吧，代码看起来可能像下面这样：
for ( int i = 0; i < 节点个数; ++i )
{
for ( int j = 0; j < 节点个数; ++j )
{
for ( int k = 0; k < 节点个数; ++k )
{
if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
{
// 找到更短路径
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
}
}
}
|
但是这里我们要注意循环的嵌套顺序，如果把检查所有节点X放在最内层，那么结果将是不正确的，为什么呢？因为这样便过早的把i到j的最短路径确定下来了，而当后面存在更短的路径时，已经不再会更新了。
让我们来看一个例子，看下图：
图中红色的数字代表边的权重。如果我们在最内层检查所有节点X，那么对于A->B，我们只能发现一条路径，就是A->B，路径距离为9。而这显然是不正确的，真实的最短路径是A->D->C->B，路径距离为6。造成错误的原因就是我们把检查所有节点X放在最内层，造成过早的把A到B的最短路径确定下来了，当确定A->B的最短路径时Dis(AC)尚未被计算。所以，我们需要改写循环顺序，如下：
for ( int k = 0; k < 节点个数; ++k )
{
for ( int i = 0; i < 节点个数; ++i )
{
for ( int j = 0; j < 节点个数; ++j )
{
if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )
{
// 找到更短路径
Dis[i][j] = Dis[i][k] + Dis[k][j];
}
}
}
}
|
这样一来，对于每一个节点X，我们都会把所有的i到j处理完毕后才继续检查下一个节点。
那么接下来的问题就是，我们如何找出最短路径呢？这里需要借助一个辅助数组Path，它是这样使用的：Path(AB)的值如果为P，则表示A节点到B节点的最短路径是A->...->P->B。这样一来，假设我们要找A->B的最短路径，那么就依次查找，假设Path(AB)的值为P，那么接着查找Path(AP)，假设Path(AP)的值为L，那么接着查找Path(AL)，假设Path(AL)的值为A，则查找结束，最短路径为A->L->P->B。
那么，如何填充Path的值呢？很简单，当我们发现Dis(AX) + Dis(XB) < Dis(AB)成立时，就要把最短路径改为A->...->X->...->B，而此时，Path(XB)的值是已知的，所以，Path(AB) = Path(XB)。
N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.
Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.