Dijkstra算法是贪心算法，是一个单源最短路算法，就是先记录下从起始点到各个点的距离，然后选择距离最小的结点，用这个最小距离加上选取的点和其他点一一比较，看看需不需要更新起点到其他点的距离，直到所有的点选完。
疑问：为什么要先选最小的点？
按下图排
如果先取小的排先是 #，10，#，30，100（把#当成是无穷大）
第二个结点的10最小，更新
得 #，10，60，30，100
接着是第四个结点30最小，更新
得 #，10，50，30，90
接着是第三个结点50最小，更新
得 #，10，50，30，60
最后由v5无更新，最终得#，10，50，30，60
如果取最大会怎么样呢？
原始序列： #，10，#，30，100（把#当成是无穷大）
取100，无更新
取30，由v4更新，得：
#，10，50，30，90
咦，我们发现在这一步就出现了问题，
首先是多了50，比30大，这就不符合取最大的规则了，当然这不是最重要的，你可能会说，我可以选回去麻，但是先不说这在算法上可不可以实现，它就算可以实现也是复杂的。
其次，第一步取最大这个情况下后面100变小了，它因为用后面的v4更新后变成了90，这会出现一种什么样的问题呢？这会让第一步的比较无效，试想会不会因为v0到v5的路径变小了，导致v0到某个结点的距离要大于v0到v5再到某个结点的距离呢？这是有可能的，当然在这个图里面没有这样的结点，但这是有可能的，对吧？
这就是错误的点了。
小朋友，相信这时候你又有了疑问，什么疑问呢？那便是，为什么从最大更新后原来到最大距离的那个结点的距离会变小呢？
有点饶，大概知道意思就好啦。
这便是因为有别的结点和源点的距离更小啊，在加上别的结点到v5结点的距离，是不是v0到v5的距离有可能会更小，有没有这种可能，有吧？
而换了从距离最小的那个结点开始比较更新，就不会有这个问题啦。
因为你想啊，如果别的结点和源点的距离更大，在加上别的结点到v5结点的距离，是不是v0到v5的距离不可能更小，不可能，对吧？这就和前面的选择不冲突了。
我想到了一个有趣的事情，如果要求当源最长路，大概就是这样反过来吧。
Floyd多源最短路算法
假如现在只允许经过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循环，代码实现如下。
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (e[i][j] > e[i][1] + e[1][j])
e[i][j] = e[i][1] + e[1][j];
}
}
接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小，代码实现为如下。
//经过1号顶点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j];
//经过2号顶点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][2]+e[2][j]) e[i][j]=e[i][2]+e[2][j];
最后允许通过所有顶点作为中转
整个算法过程虽然说起来很麻烦，但是代码实现却非常简单，核心代码只有五行：
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
这段代码的基本思想就是：最开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前k号点的最短路程。
另外需要注意的是：Floyd-Warshall算法不能解决带有“负权回路”（或者叫“负权环”）的图，因为带有“负权回路”的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->…->1->2->3这样路径中，每绕一次1->-2>3这样的环，最短路就会减少1，永远找不到最短路。其实如果一个图中带有“负权回路”那么这个图则没有最短路。
看了这里，首先有一个疑问：怎么这个三重循环的两个节点之间只更新了1次？只能有两段边或者是一段边的情况么？显然不是的。
为什么不是呢？我们先一个个分析，当k中转站只有一个的时候，显然是这样的。但是当k有多个的时候就不是这样子的了。
为啥不是呢？我看着这个循环就像只更了一次啊。
小朋友，那你有木有注意到它里面也是有两个循环滴，好像不好理解喔。
更新就更新，你用两个循环是啥意思呢？
这就是问题的切入点了。
这我们只能从每一个循环开始看，假如只允许一个结点进行中转，e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点，再从1号顶点到j号顶点的路程之和。而两重循环把n个顶点之间的联系都遍历了一遍，可以得出是否需要经过中转最短。
我们可以假设有4个顶点，v1,v2,v3,v4.。
把v1看成是中转的顶点v2到v3的最短路为2 1 3
v2到v4的最短路为2 4
如果把v3变成是可以中转的顶点，是不是有这样子的可能，v2到v4之间的最短路可以是 2 1 3 4，有这种可能，对吧？
那这在两个两重循环里面是怎么体现的呢？一个两重循环可以理解，那两个，n个要怎么理解呢？
从两个开始说起吧，我们需要理解两个顶点之间是怎么出现3条边和两个顶点的。
以我们上面说的四个结点为例子，首先，把v1当成是中转站，e[2][3]=e[2][1]+e[1][3]，没问题，对吧。
进入到第二个二重循环，把v3加入作为中转站，e[2][4]=e[2][3]+e[3][4]，再把e[2][3]展开就对了。
这就是最外层循环和里面两重循环的联系了，外面的循环将里面的两重循环后的值发生了变化，一直变化着，一步步迭代更新。
小朋友，你好像又有了新的疑问，那个，为什么单源最短路需要从和源点距离最短的的结点开始选择，而这种算法却不用把中转结点也这样子选更新的结点呢？
哎，其实是不一样的，哪里不一样呢？
首先，你有没有发现，Dijkstra算法里面的v0（源点）并不是中转点，Dijkstra算法的中转点是从和源点距离最短的的结点开始递增地一个个选择的，这就让它的中转点不能乱选，不然可能前面的选择就无效了（前面已经分析过了）。
而为什么Floyd算法就可以乱选呢？首先它的中转点是确定的，再随意选择源点和终点，当也不是随意的，因为最后它都会把所有的源点和终点通过两重循环选完。
而它们两两之间在每个二重循环里面是不冲突的，因为只有一个中转点。
如果加入了中转点，它也是不冲突的，它一遍遍地更新了最短路。
你可能会想，你前面举的例子的终点改变了（把3改成了4），那如果不变呢？
好，我们来看不变的情况。我们用v3作为第一个中转的结点
e[2][7]=e[2][3]+e[3][7]假设更新了，经过v3是2到7的最短路。
再加上v4作为中转，我们发现它也是不冲突的。
我们可以对e[3][7]进行更新，也可以对e[2][7]=e[2][4]+e[4][7]进行更新。
哇，你可能会想，哇，它变了，可能冲突了哇。
可系，真的吗？
反正怪怪的。
其实没有的，先是可能e[2][7]=e[2][3]+e[3][7]，然后可能更新为e[2][7]=e[2][4]+e[4][7]
冲突在哪里？没有吧，这个算法只是穷举了所有的情况。
你可能还有一个问题，这是什么破算法，我直接用Dijkstra算法遍历n次来不就完了吗？
额，问题是不一定好啊，而且想把复杂度降下来，程序写起来还蛮复杂的。后面有时间再想吧。
好了，吐血三升，一个三个循环的算法，居然想了半天，罢辽，罢辽，还有问题也不想辽。
注意：如果两个顶点之间没有边的话，应该定义为正无穷，后面才能慢慢变小。
Prim算法也是贪心算法来着，是从顶点开始选取的，这和kruskal算法有很大区别。
Kruskal算法，将森林合并成树。起始的每个结点它也当成是一个树。先把所有权重的边都选出来（因为是森林，所以不能只取一边） ，不构成回路就行，直到 V-1条边和边集合中没了元素，构成回路的边扔掉。
简单说，就是不断地把最小边选出来，并且不能构成回路，最后选到V-1条边就没了，再选就一定会构成回路。这就能将多个结点并成一棵树了。
