返回信息流Dijkstra对具有负边值得图是无效的。
对于负边值得图：
1. 开始时，把s放进队列
2. 在每一阶段让一个顶点v出队，找出所有与v邻接的顶点w，使得dw > dv + c(v,w)。更新这些点的dw和pw，并在w不在队列中的时候把它入队。（可以为每个顶点设置一个比特位以指示它是否在队列中）。
3. 重复以上过程直到队列为空。
void weightedNegative(Vertex s){
Queue<Vertex> q = new Queue<>();
for each Vertex v
v.dist = INFINITY;
s.dist = 0;
q.enqueue(s);
while(!q.isEmpty()){
Vertex v = q.dequeue();
for each Vertex w adjacent to v
if(v.dist + cvw < w.dist){
w.dist = v.dist + cvw;
w.path = v;
if(w is not already in q)
q.enqueue(w);
}
}
}
每个顶点最多可以出队|V|次，使用邻接表的话，运行时间为O(|E|*|V|)。
数据结构与算法分析上是这么写的。。想不太明白这个循环能走下去么。。。
比如最开始把s 节点入队，然后开始循环，出队的就是s，这时候v=s。对于s的临节点来说，T[v]=T[s]=0, Cvw=Csw=T[w].dist. 所以v.dist + cvw < w.dist永远不可能成立。循环就结束了。。。
不知道是我愚钝想错了还是这块有问题。。不知道改成<= 是否可行
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #90668同步于 2016/7/30
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】具有负边值的图单元最短路径问题，求解惑
ztd9071
2016/7/30镜像同步5 回复
订阅后，新回复会通过你的通知中心匿名送达。
5 条回复
这不就是bellman-Ford嘛
你没看到最开始除了source之外，dist都设成∞了啊，0+edge_cost < ∞，为什么会不成立呢？
改成<=是否可行 -------> 当然不可行了，这样会死循环的
【 在 winoros 的大作中提到: 】
: 这不就是bellman-Ford嘛
: 你没看到最开始除了source之外，dist都设成∞了啊，0+edge_cost < ∞，为什么会不成立呢？
: 改成<=是否可行 -------> 当然不可行了，这样会死循环的
奥，你说得对，我把输入想错了
【 在 spicewolf 的大作中提到: 】
: 这个不是bellman ford, lz去看一下spfa吧。程序确实有问题。有可能会死循环。
谢谢~