还是用数组dis来存1号到其余各点的初始路程：
既然是求最短路径，那先选一个离1号最近的结点，也就是2号结点。这时候，dis[2]=1 就固定了，它就是1到2的最短路径。这是为啥？因为目前离1号最近的是2号，且这个图的所有边都是正数，那就不可能能通过第三个结点中转使得距离进一步缩短了。因为从1号出发已经找不到哪条路比直接到达2号更短了。
选好了2号结点，现在看看2号的出边，有2->3和2->4。先讨论通过2->3这条边能否让1号到3号的路程变短，也即比较dis[3]和dis[2]+e[2][3]的大小。发现是可以的，于是dis[3]从12变为新的更短路10。同理，通过2->4也条边也更新下dis[4]。
松弛完毕后dis数组变为：
接下来，继续在剩下的 3 4 5 6 结点中选一个离1号最近的结点。发现当前是4号离1号最近，于是dis[4]确定了下来，然后继续对4的所有出边看看能不能做松弛。
balabala，这样一直做下去直到已经没有“剩下的”结点，算法结束。
这就是Dijkstra算法，整个算法的基本步骤是：
所有结点分为两部分：已确定最短路的结点集合P、未知最短路的结点集合Q。最开始，P中只有源点这一个结点。（可用一个book数组来维护是否在P中）
在Q中选取一个离源点最近的结点u（dis[u]最小）加入集合P。然后考察u的所有出边，做松弛操作。
重复第二步，直到集合Q为空。最终dis数组的值就是源点到所有顶点的最短路。
代码：
for(int i = 1; i <= n; i++) dis[i] = e[1][i]; //初始化dis为源点到各点的距离 for(int i = 1; i <= n; i++) book[i] = 0; book[1] = 1; //初始时P集合中只有源点 for(int i = 1; i <= n-1; i++) //做n-1遍就能把Q遍历空 { int min = INF; int u; for(int j = 1; j <= n; j++) //寻找Q中最近的结点 { if(book[j] == 0 && dis[j] < min) { min = dis[j]; u = j; } } book[u] = 1; //加入到P集合 for(int v = 1; v <= n; v++) //对u的所有出边进行松弛 { if(e[u][v] < INF) { if(dis[v] > dis[u] + e[u][v]) dis[v] = dis[u] + e[u][v]; } } }Dijkstra是一种基于贪心策略的算法。每次新扩展一个路径最短的点，更新与它相邻的所有点。当所有边权为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程就确定下来了，这保证了算法的正确性。
但也正因为这样，这个算法不能处理负权边，因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路程不会改变的性质。
于是，Bellman-Ford算法华丽丽的出场啦。它不仅可以处理负权边，而且算法思想优美，且核心代码只有短短四行。
（用三个数组存边，第i条边表示u[i]->v[i]，权值为w[i]）
for(int k = 1; k <= n-1; k++) for(int i = 1; i <= m; i++) if(dis[v[i]] > dis[u[i]] + w[i]) dis[v[i]] = dis[u[i]] + w[i];后两行代码的意思是，看看能否通过u[i]->v[i]这条边缩短dis[v[i]]。加上第二行的for，也就是把所有的m条边一个个拎出来，看看能不能缩短dis[v[i]]（松弛）。
那把每一条边松弛一遍后有什么效果呢？
比如求这个例子：
同样用dis数组来存储1号到各结点的距离。一开始时只有dis[1]=0，其他初始化为INF。
先来处理第一条边 2->3 ，然鹅dis[3]是INF，dis[2]+2也是INF，松弛失败。
第二条边 1->2 ，dis[2]是INF，dis[1]-3是-3，松弛成功，dis[2]更新为-3。
就这样对所有边松弛一遍后的结果如下：