详尽的解释一下pascal里什么是负权图吧~负代表的是方向还是数值？怎么知道什么时候用spfa？？谢~

Question

如题所述

Answer 1

负权图就是存在一条边 a点指向b点 且他的权值是负的
负权代表的是数值的正负
至于spfa 他可以用以绝大多数情况
这里给LZ解释下spfa不适用于什么时候吧

他的时间复杂的是O(m*k) 这里M是边的条数 K可以理解为一个常数
因为spfa是动态维护最短路 所以对于一个节点入队次数越少 他的时间复杂度就越小
也就是说 只要图越稀疏 spfa的时间复杂度就越低 K的值就越小
所以 spfa适用于比较稀疏的图 在稠密图里 spfa容易超时

spfa可以处理负权图 因为他是动态维护了最短路 所以用spfa时不需要考虑是否存在负边

spfa可以处理负环 需要注意的是 可以处理负环 不代表他能求出有负环的图的最短路 他只是能判断是否存在负环

不懂可追问追问

感谢，看懂了

我照着百科上打得，结果输入负权时要么201错误（freepascal），要么死循环，，why

追答

应该是出现负环了吧 201估计是负环里出现了重复入队 然后队列爆了
死循环同理

追问

能给个样例不，，有追加哦，亲

带负权的

追答

n=8 m=10
1 5 2
1 2 1
2 3 2
3 4 -1
3 6 1
4 7 1
4 5 1
6 7 1
6 8 1
7 8 5
每行的3个数x,y,z表示x到y 有一条长时z的边
是无向图
结果是4

Answer 2

是负权圈吧，这个貌似是指一个图内有两点之间有一个圈然后这个圈的权是负的，
A->0->B 用0 代表这个圈的话就会是A-B的路程最小不确定 即每绕负权圈（也就是那个0）一圈就会变得更小，所以无法求出A->B的最短路程
SPFA貌似在图中没有负权圈就可以用