level 13
有木有人啊
2012年10月21日 14点10分
level 7
level 6
edge[s][j]+edge[j][u]>=shortest_dist[u]
这是著名的三角不等式
dist[j]+edge[j][u]<dist[u]
这里是 松弛(relax) 操作的判断句,松弛 是Bellman-Ford,Dijkstra,SPFA等算法的核心
level 12
level 8
要理解算法是什么原理啦。。
dij是贪心，每次只选择未确定下来答案的、距离原点最近的点往外扩展更新，也就是每次都能确定一个点到原点的最终答案，并且这个值确定下来之后不会改变。在边权非负的情况下，每次确定的答案一定是递增的。所以对于某个点来说，它的dist一定是周围已经确定了dist的那些点更新的，而未确定dist的点无权更新它（而且因为它先被确定而周围的点在其后，所以它们的dist也一定比它的dist要大）。但是有负边权之后构造一个反例非常容易。
ford（应该叫floyd）是动态规划，我们看见的f[i,j]=min(f[i,j],f[i,k]+f[k,j])只是其简化版本，原版的floyd是三维的。f[i,j][k]表示：从i走到j只经过【前k个点】中的某些点，得出的最短路。每次k+1之后执行那个式子，相当于用点k来松弛i~j这条路径（类似于f[k]=opt{f[k-1]}——这里f的每个元素是一个矩阵——这就是为什么一定要先循环k），所以最终i~j这条路径被所有点松弛了一遍，也就是“从i~j经过任意某些点的最短路”，也就是最终i~j的最短路了。人们发现，在k的每遍循环中，f[i,j]仅被更新了一次，换句话说f[i,j][k]仅与f[i,j][k-1]有关。所以k那一维空间可以节约掉，就变成现在这样了。
2012年10月21日 15点10分
7
dij是贪心，每次只选择未确定下来答案的、距离原点最近的点往外扩展更新，也就是每次都能确定一个点到原点的最终答案，并且这个值确定下来之后不会改变。在边权非负的情况下，每次确定的答案一定是递增的。所以对于某个点来说，它的dist一定是周围已经确定了dist的那些点更新的，而未确定dist的点无权更新它（而且因为它先被确定而周围的点在其后，所以它们的dist也一定比它的dist要大）。但是有负边权之后构造一个反例非常容易。
ford（应该叫floyd）是动态规划，我们看见的f[i,j]=min(f[i,j],f[i,k]+f[k,j])只是其简化版本，原版的floyd是三维的。f[i,j][k]表示：从i走到j只经过【前k个点】中的某些点，得出的最短路。每次k+1之后执行那个式子，相当于用点k来松弛i~j这条路径（类似于f[k]=opt{f[k-1]}——这里f的每个元素是一个矩阵——这就是为什么一定要先循环k），所以最终i~j这条路径被所有点松弛了一遍，也就是“从i~j经过任意某些点的最短路”，也就是最终i~j的最短路了。人们发现，在k的每遍循环中，f[i,j]仅被更新了一次，换句话说f[i,j][k]仅与f[i,j][k-1]有关。所以k那一维空间可以节约掉，就变成现在这样了。
他说"都是if(dist[j]+edge[j][u]<dist[u]）么",目测ford是指bellman-ford而不是floyd
2012年10月21日 15点10分
回复 奇特空 :好吧，bellman-ford我们都没学，直接被某学长带着学SPFA。。目测ford和floyd原理类似，也是某条路径被所有点松弛了一遍。。
2012年10月21日 15点10分
回复 RexSkz :ford和flyod差多了吧......ford就是对每条边不停地松弛,当你觉得松弛得不能再松弛的时候就可以收手了......效率低得无法直视,你们学长的做法是正确的
2012年10月21日 15点10分
回复 奇特空 :好吧没学就是不行>_<。。个人觉得SPFA当做一个全新的算法学也没什么问题。。
2012年10月21日 15点10分
level 8
佛洛依德可以在负权图中用吗
2012年10月21日 17点10分
8
应该是ford，bellmanford
2012年10月22日 03点10分
floyd有负边肯定跪。。
2012年10月22日 10点10分
