图中节点之间的权重不同。这样任意两点之间的最短距离就不是广度优先搜索可以求出来的。
因为如果权重不同，所以路径上点的个数不等于距离，那么环中节点的到起始节点的距离就需要随着路径的不同而变化多次。
节点属性
每个节点多两个额外的属性：
- 父节点
v.parent()
也就是从其实点到该节点目前的最短路径上，该点的父节点。（有目前两个字，是因为，这个父节点会改变） - 最短路径
v.d()
从其实点到该节点目前的最短路径上，该点到起始点的距离。（同上）
环和权重
假设起始点为A，在遍历的时候B与A之间的最短距离在某一路径上被设置为n，然后B之后的节点C在n的的基础上加上BC的距离，也就是n+bc。只有又有一天路径到达B，发现距离比n小，所有更改B到A的距离，但是C没有改变。
所以需要多次遍历。
而这种情况多是由于环和权重不同的存在发生的。
比如A->B(4)->C(3)，A->D(1)->E(1)->B(1)。(括号内为父节点到本节点的权重，或是距离)
在这条环上，B的到A的最短距离就会由4（A->B）改为3（A->B->E->B）。
负权重和环
负权重和存在在一个环内的时候，从某个点出发绕回该点，可能的强狂：
- 该环的总权重>=0
那么对最短距离没有影响。因为最短路径每次都需要判断，所以如果大于或等于当前存储的最短路径，那么不会引起该节点的属性变化。
但是没有办法记录多条距离相同的路径。 - 该环的总权重<0
那么每次遍历，节点的最短路径和父节点都会变化，都会变小。
假设存在节点N->M，那么:M到起始点的最短距离<=N到起始点的最短距离+NM之间的距离。
因为，如果M父节点是N，那么上述公式等号成立。
如果M的节点父节点不是N，那么应该是小于。
只有当N处在一个负权重的环路中，那么在最后一次遍历的时候N到起始点的最短距离改变，减小。但是没有影响到M。此时就会发生，上述情况，子节点到父节点的最短距离大于其父节点到起始点的最短距离+两节点之间的距离。原因只是，每次遍历，负权重环中的点的最短距离都会改变，而其出点的点有一部分是来不及发生变化的（总是在下一次遍历的时候才能变化）。
N->M:M.d > N.d+nm可以判断出现负权重环。
Bellman Ford算法O(VE)
可用于有向带权重，有环的图
依次遍历每个节点：改变其指向点的v.d()，始终设置最小的，同时改变v.parent().
遍历图的节点数v-1次。
为什么是节点数v-1:********************************
最后在遍历一次判断是否存在负权重环
拓扑排序寻找最短路径
适合与有向带权重，无环图
首先对图进行拓扑排序。在排序结果中，起始点之前的点视为起始点不可达的点。
然后从起始点开始向后进行松弛操作。
Dijkstra
相当于一种改进的Bellman Ford算法
适用于正权重
Bellman Ford算法，在处理完一个点以后，是按照图中节点的顺序选择下一个点，或者说是随机的，没有特选的选择。
而Dijkstar算法，在一个节点对其所有指向的点处理完毕以后，是有选择的去选取下一个要处理的点：选取的是目前已确定的，到起始点最短距离的点。
例如下面：
A为起始点，其指向：A->B(2),A->C(3),A-D(4)，处理完A以后将A标记为已删除。
那么下一次选取起始点为B：B->E(2),B->F(3);B处理完以后，目前到起始点距离最短，还没有被处理的点是C(3),E(2+2)。所以选取C点为下一个要处理的点。
永远选取：没有被处理且目前距离起始点距离最短的点为下一个要处理的点。
（这一张还有一个差分约束和最短路径，貌似和线性规划有关）
网友评论