//参数：所有点的集合，所有边的集合，源点 functionBellmanFord(listvertices, listedges, vertexsource) //需要的变量： //（u，v）的权值 w //数组weight[]，源点到每个顶点的最短路 //数组predecessor[]，在最短路中，每个顶点的前继
// Step 1: 对图进行初始化 foreach vertex v in vertices: if v is source then weight[v] := 0 else weight[v] := infinity predecessor[v] := null
// Step 2: 不断松弛每条边，重复|V|-1次 for i from1to size(vertices)-1: //下面松弛每一条边，可以使用二重循环处理 foreach edge (u, v) with weight w in edges: if weight[u] + w < weight[v]: weight[v] := weight[u] + w predecessor[v] := u
// Step 3: 检查是否有负权回路 foreach edge (u, v) with weight w in edges: if weight[u] + w < weight[v]: error "Graph contains a negative-weight cycle" return weight[], predecessor[]
##证明 The correctness of the algorithm can be shown by induction. The precise statement shown by induction is:
Lemma. After i repetitions of for cycle:
If Distance(u) is not infinity, it is equal to the length of some path from s to u; If there is a path from s to u with at most i edges, then Distance(u) is at most the length of the shortest path from s to u with at most i edges. Proof. For the base case of induction, consider i=0 and the moment before for cycle is executed for the first time. Then, for the source vertex, source.distance = 0, which is correct. For other vertices u, u.distance = infinity, which is also correct because there is no path from source to u with 0 edges.
For the inductive case, we first prove the first part. Consider a moment when a vertex’s distance is updated by v.distance := u.distance + uv.weight. By inductive assumption, u.distance is the length of some path from source to u. Then u.distance + uv.weight is the length of the path from source to v that follows the path from source to u and then goes to v.
For the second part, consider the shortest path from source to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from source to v is the shortest path from source to v with at most i-1 edges. By inductive assumption, v.distance after i−1 cycles is at most the length of this path. Therefore, uv.weight + v.distance is at most the length of the path from s to u. In the ith cycle, u.distance gets compared with uv.weight + v.distance, and is set equal to it if uv.weight + v.distance was smaller. Therefore, after i cycles, u.distance is at most the length of the shortest path from source to u that uses at most i edges.
If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices v[0], …, v[k−1],
v[i].distance <= v[(i-1) mod k].distance + v[(i-1) mod k]v[i].weight
Summing around the cycle, the v[i].distance terms and the v[i−1 (mod k)] distance terms cancel, leaving
0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight
I.e., every cycle has nonnegative weight.
##检测负权回路
When the algorithm is used to find shortest paths, the existence of negative cycles is a problem, preventing the algorithm from finding a correct answer. However, since it terminates upon finding a negative cycle, the Bellman–Ford algorithm can be used for applications in which this is the target to be sought - for example in cycle-cancelling techniques in network flow analysis.
##在路由上的应用
A distributed variant of the Bellman–Ford algorithm is used in distance-vector routing protocols, for example the Routing Information Protocol (RIP). The algorithm is distributed because it involves a number of nodes (routers) within an Autonomous system, a collection of IP networks typically owned by an ISP. It consists of the following steps:
Each node calculates the distances between itself and all other nodes within the AS and stores this information as a table. Each node sends its table to all neighboring nodes. When a node receives distance tables from its neighbors, it calculates the shortest routes to all other nodes and updates its own table to reflect any changes. The main disadvantages of the Bellman–Ford algorithm in this setting are as follows:
It does not scale well. Changes in network topology are not reflected quickly since updates are spread node-by-node. Count to infinity (if link or node failures render a node unreachable from some set of other nodes, those nodes may spend forever gradually increasing their estimates of the distance to it, and in the meantime there may be routing loops).
###报名 一周前，记不清通过什么渠道知道了这么一场黑客马拉松的活动，当然也叫创客马拉松。活动大概是这么宣传的：两天时间内，报名参加的选手想一些 idea ，然后可以获得现场导师的帮助，再经过好多轮迭代最后完成项目，做出产品，或者是 demo 。主办方在 SJTU 承包了个食堂做场地，然后我和一个小伙伴就乐呵乐呵凑热闹去了。
###Day one 第一天中午开始，到了之后进一步了解到，直白的说，就是那么多人产生一些创意，然后自由组队，然后做项目。但是作为一个没有开发经验的小白，实在不知道怎么办了，于是就思考一下别人提供的点子，感觉没有十分合适的，就准备随意聊聊天回去了。开始之前，有几位嘉宾导师发言，讲了些设计模式之类的内容，要我们着眼于‘大局’，而不是某种语言某种技术。这点还是值得思考的。
在我看来这就是写一个编译器呗，当然，我还不会写。我的小伙伴的想法是:把这个语言（比如D语言）的关键字使用 C 的宏替换成 C 的关键字，这样转换成的 C 程序，在调用gcc编译。我觉得这个想法不是很可行。需要考虑的东西比较多，或许学完编译原理好后直接就写个简单编译器即可。A 自己也没什么思路，最后不了了之。
一位导师倒是提供了一个信息：Ragel State Machine Compiler. 这个开源软件好像可以实现一些上述功能。这个也留着以后研究。
傍晚时分， 准备离开的时候，遇到了两个创客，交谈甚欢，产生了一些基于硬件的想法，最后决定做一个简单demo，并且取名 Health Cloud,然后可以衍生这个‘健康云’的应用场景，等等。交谈的过程中，知道了LiveCode这种用于快速开发的编程语言，并且能转化为任何平台的原生程序。不过确实小众。
###Dat two 经过合计约十五小时的现学现卖，查找资料以及努力调试，终于做成一个简单的 demo ，现记录下来，以便日后还原以及改进。
