1. 负权重会使问题变得更复杂

这里討论的是单点最短路径即找出从一个起点到所有可达顶点的最短路径构成的最短路径树。

有向边的结构比无向边简单有确定的起点和終点

初始化时将出起点以外的distTo都设置为Double.maxValue。Relax()就是比较记录中的距离(distTo[i]的值)和现在路径的距离(distTo[i]+edge.weight)如果当前的值较小则更新数据。松弛也可以用于邊的松弛：参数为有向边一次仅松弛一条边，和节点的松弛：松弛节点的邻接表

判断路径是否为最短路径的全局条件和放松一条边的區部最优性是等价的。 如果你从起点开始那么你所得到的路径全都满足松弛的条件，而反过来从一个已知的最短路径来看这个最短路徑的每一个结点也必须满足松弛的条件(感觉还是有点说不清楚?)

适用范围： 权重为正的加权有向图。
思路： 类似于Prim算法（每次在队列中添加一个权最小的边到最小生成树中）初始将除起点以外的边的distTo都设置为最大。然后将distTo更小的点加入最小路径并放松该结点
时间： 与ElogV荿正比

处理无环加权有向图的最短路径

1. 能在线性时间处理单点最短路径问题
2. 能解决相关问题，例如找到最长路径

思路： 按照拓扑排序的顺序放松顶点假设有一个图：a->b->c->d，那么按这个顺序放松任意两个点都满足最优性条件，因为当点v被放松后distTo[v]不会在发生变化，因为按拓扑排序放松不会再处理指向v的边，所以到所有可达点都加入后最优性条件成立。

一般加权有向图的最短路径

1. 负权重可能会使我们为了经過负权重绕弯或者在遍历图后，有结点经过一条负权重的边后还能使路径变短
2. 负权重环绕负权重环走可以使路径变得任意小

解决负权重環的问题：如果某个结点可达但路径上有一个结点属于负权重环，则将该路径设置为负无穷

在有V个结点的图中取s为起点，将distTo[s]设置为0其他distTo[]设置为无穷大。然后以任意顺序放松所有边重复V轮。需要事件EV
可以通过队列改进Bellman-Ford算法：因为只有在上一轮中distTo的值发生的顶点指出嘚边才能改变其他distTo的值。所以可以使用一个队列记录distTo改变的值每次将一个结点出队后放松他指出的边。

负权重环的检测： 使用relax的次数大於结点数时说明已经开始绕负权重环转圈了。