只想说：温故而知新，可以为师矣。我大二的《数据结构》是由申老师讲的，那时候不怎么明白，估计太理论化了(ps：或许是因为我睡觉了)；今天把老王的2011年课件又看了一遍，给大二的孩子们又讲了一遍，随手谷歌了N多资料，算是彻底搞懂了最短路径问题。请读者尽情享用……
我坚信：没有不好的学生，只有垃圾的教育。不过没有人理所当然的对你好，所以要学会感恩。
一.问题引入
二.Dijkstra算法
该算法在《数据结构》课本里是以贪心的形式讲解的，不过在《运筹学》教材里被编排在动态规划章节，建议读者两篇都看看。
观察右边表格发现除最后一个节点外其他均已经求出最短路径。
S：已求出最短路径的顶点的集合V-S=T：尚未确定最短路径的顶点集合
(2) 求最短路径步骤
下面是上图的求解过程，按列来看，第一列是初始化过程，最后一行是每次求得的next点。
(3) 问题：Dijkstar能否处理负权边？(下面的解释引自网上某大虾)
答案是不能，这与贪心选择性质有关(ps：貌似还是动态规划啊，晕了)，每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点（dmin’），再通过这个负权边L(L<0)，使得路径之和更小（dmin’+L<dmin）,则dmin’+L成为最短路径，，并不是dmin，这样dijkstra就被囧掉了。比如n=3，邻接矩阵：0，3，43，0，-24，-2，0,用dijkstra求得d[1，2]=3，事实上d[1，2]=2，就是通过了1-3-2使得路径减小。不知道讲得清楚不清楚。
二.Floyd算法
参考了南阳理工牛帅(目前在新浪)的博客。
Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点到B，所以，我们假设dist(AB)为节点A到节点B的最短路径的距离，对于每一个节点K，我们检查dist(AK) + dist(KB) < dist(AB)是否成立，如果成立，证明从A到K再到B的路径比A直接到B的路径短，我们便设置 dist(AB) = dist(AK) + dist(KB)，这样一来，当我们遍历完所有节点K，dist(AB)中记录的便是A到B的最短路径的距离。
很简单吧，代码看起来可能像下面这样：
for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) { for (int k=0; k<n; ++k) {if (dist[i][k] + dist[k][j] < dist[i][j] ) {dist[i][j] = dist[i][k] + dist[k][j];} } }}
但是这里我们要注意循环的嵌套顺序，如果把检查所有节点K放在最内层，那么结果将是不正确的，为什么呢？因为这样便过早的把i到j的最短路径确定下来了，而当后面存在更短的路径时，已经不再会更新了。
让我们来看一个例子，看下图：
图中红色的数字代表边的权重。如果我们在最内层检查所有节点K，那么对于A->B，我们只能发现一条路径，就是A->B，路径距离为9，而这显然是不正确的，真实的最短路径是A->D->C->B，路径距离为6。造成错误的原因就是我们把检查所有节点K放在最内层，造成过早的把A到B的最短路径确定下来了，当确定A->B的最短路径时dist(AC)尚未被计算。所以，我们需要改写循环顺序，如下：
ps：个人觉得，这和银行家算法判断安全状态(每种资源去测试所有线程)，树状数组更新(更新所有相关项)一样的思想。
for (int k=0; k<n; ++k) { for (int i=0; i<n; ++i) { for (int j=0; j<n; ++j) {/*实际中为防止溢出，往往需要选判断 dist[i][k]和dist[k][j都不是Inf ，只要一个是Inf，那么就肯定不必更新。 */if (dist[i][k] + dist[k][j] < dist[i][j] ) {dist[i][j] = dist[i][k] + dist[k][j];} } }}走走停停，不要害怕错过什么，
