解析Bellman-Ford算法求最短路径

        下面说明下dijkstra算法和Bellman-Ford算法的求解，而dijkstra算法无法求解负权图的原因吧！请看下图（本图片来自百度文库 用户： 1107905594）

• 下Bellman-Ford算法基本思想

•  Bellman-Ford算法的基本步骤

            1、首先将所求起点s到图中的各点距离用数组dist[n]存储起来，如果两边可达，则dist[i]=Edge[s][i]，否则则灵dist[i]=maxm，（maxm为一个无穷大值，根据需要设定数值），（注意：这里假设不允许顶点自身可达）。

            2、然后通过通过循环n-2次找出含有最多含有n-1条边的路径的最小路径数组path[u]=v，这个数组也是通过保存当前顶点v的最短路径前缀u。最后也是通过读取前缀得出一条路径。由于第一步将第一条边已经保存下来，所以这里只须循环n-2次就可以了。这一步很关键，因为这一步是说怎么去找出每个节点的最短路径的呢？然而，在n-2次循环中，每循环一次，他都将保存好当前节点v离始点的最短距离的前缀u，所以一维数组path[n]保存了图中所有可达节点到节点v的最短路径前缀。最后就得到结果path[n]。

           代码的编写就不写了，借别人的用一下。

本博文翻译于一 百度文库用户，有侵权之处请见谅，通知本人删除。