BellmanFord算法
Bellman-Ford算法是一个单源点最短路径算法，这个算法的目的就是找到整个图，，到起始节点（自己定的）最短的路径和路径长度。
优点/缺点
优点
这个算法的优点应该是相对Dijkstra算法来说的，就是可以有负权值路径并且能检测到图中是否有负权值回路。
缺点
缺点就是虽然能检测负权值回路，但是解决不了有负权值回路的最短路径问题。 还有就是时间复杂度比较高。 O(|V| * |E|).
实现
其实实现的原理就是：每次对当前整个图进行一次松弛操作。一共进行|V|次。 每次的松弛操作都是|V|-1次的松弛判断。
下面是代码实现：
;Vertex;struct LinkList{int val;int weight;LinkList * next;LinkList(int v, int w): val(v), weight(w), next(NULL){}};typedef LinkList* VList;struct TableEntry{VList Header;Vertex Dist;Vertex Path;};typedef TableEntry Table[NumVertex+1];void InitTable(Vertex start, Table T){int OutDegree = 0;VList temp = NULL;for (int i = 1; i <=NumVertex; i++) {T[i].Header = NULL; // init the vertexT[i].Dist = Infinity;T[i].Path = -1;scanf(“%d”,&OutDegree);for (int j = 0; j < OutDegree; j++) { // init the link vertextemp = (VList)malloc(sizeof(struct LinkList));scanf(“%d %d”, &temp->val, &temp->weight);temp->next = T[i].Header;T[i].Header = temp;}}T[start].Dist = 0;}void PrintPath(Vertex V, Table T){if (T[V].Path != -1) {PrintPath(T[V].Path, T);printf(” to “);}printf(“%d”, V);}bool BellFord(Vertex start, Table T){bool Update = false;VList temp;for (int i = 1; i <= NumVertex; i++) { //cycle the num of vertexUpdate = false;for (int j = 1; j <= NumVertex; j++) { // traversal all the vertexif (T[j].Dist != Infinity) { // if the current vertex distance is not Inftemp = T[j].Header;while (temp != NULL) { // if it have traversaled the link vertexif (T[j].Dist + temp->weight < T[temp->val].Dist) { //if need to relaxT[temp->val].Dist = T[j].Dist + temp->weight; //relax operationT[temp->val].Path = j; // mark the pathUpdate = true; // mark the vertex update is true}temp = temp->next; // find the next node}}}}if (Update == true) {return false; // if the Graph have a negative cycle}else{return true; // no negative cycle}}int main(int argc, const char * argv[]) {Table T;InitTable(1, T);if (!BellFord(1, T)) {printf(“There is a cycle!\n”);return 0;}PrintPath(3, T);return 0;}测试用例：case:—10
上面的图就是： 节点1 -> 2(-1)->3(1) 节点2->3(-2)->4(1) 节点3->4(-1) 节点4
如果你曾歌颂黎明，那么也请你拥抱黑夜
