------Bellman-Ford--

用于解决图中没有负环的最短路径问题

“松弛”函数:

对于该算法，需要用到“松弛”的函数，在图中我将维持着一个v.d的属性（v∈G.V）。用来记录从源结点s到结点v的最短路径权重的上限。v.d就是s到v的最短路径估计（v.d将会不断被更新）。 那么我需要对最短路径估计和前驱结点进行初始化，下面为初始化的初始化的伪代码：

1. INITIALIZE SINGLE SOURCE ( G,s)
2. For each vertex v ∈ G.v

3.     v.d  = ∞
   

4.     v.π = NIL
   

5. s.d = 0 该算法的运行时间为O（V）

在初始化后，我们还需要一个“松弛”函数，对于每一个边进行松弛。其目的不断地测试一下是否可以从s到v的最短路径进行改善。

松弛测试方法：

将从结点s到结点u之间的最短路径距离加上结点u到结点v的权重，并与当前的s到v最短路径进行比较，如果前者小，则对v.d和v.π进行更新。 松弛的步骤可以降低最短路径的估算值v.d和更新v的前去属性π。

松弛的伪代码：

1. RELAX( u, v, w )
2. If ( v.d > u.d + w(u, v)

3. v.d = u.d + w(u,v)
   

4. v.π= d
   

该算法的运行时间为O（1）

Bellman-Ford算法:

考虑到从源结点s到任意的的结点v有任意的一条路径，而且最短路径都是简单的路径，所以该路径最多包含|V|-1条边（没有环路）。所以我们只需要对每条边松弛|V|-1次。 经典的Bellman-Ford算法变可以实现这种单源最短问题。

Bellman-Ford算法的伪代码：

1. Bellman-Ford(G,s,w)
2. INITIALIZE SINGLE SOURCE ( G,s)
3. For 1 to |G.V| - 1

4.  For each edges (u,v) ∈G.E
   

5.        RELAX( u, v, w )
   

6. For each edges (u,v) ∈G.E

7.  If ( v.d > u.d + w(u,v) )
   

8.       Return false
   

9. Return ture

该算法的第2行运行时间为O(|V|-1),而4到5行的运行时间为O（E），第6行的运行时间为O（E），所以该算法的总运算时间为O(VE)。

代码中图的数据结构:

该算法是在图的数据结构上运算，是用邻接链表的方式来储存数据。 个人在设计图的数据结构时候，采用一个包含|V|条链表的数组Adj所构成，每个结点u都有一个链表，所以数组为Adj[u]储存所有的结点，并且为图的一个属性，链表结点的属性包括v.data(储存的数据),v.d(最短路径估计)，v.weight(边u到v的权重)，v.π（v的前驱结点），v.next（v的下一个结点）

使用说明：

使用者只需要只需要在Main函数中初始化图的结点之间的连接和边的权重（u,v,weight）,同时更新图的Graph构造函数中图的结点数量G->n和边的数量G->e。

测试：

Test:测试部分或者断点部分都在源代码的注释中以//test为标注。使用者可以自行测试

维护：

维护该代码因看用户的需求，如果图的边e远远小于v²，则继续采用邻接链表的数据结构，如果图的边e大于v²，则采用邻接矩阵的数据结构储存。关于核心算法Bellman-Ford根据伪代码进行修改则行。