spfa判断负环 代码注释 golang
作者:
望哥
,
2020-07-15 19:58:35
,
所有人可见
,
阅读 710
package main
import(
"fmt"
"bufio"
"os"
)
const N=2010
const M=10010
const Max = 10000 * N // 最大距离
var(
reader = bufio.NewReader(os.Stdin)
writer = bufio.NewWriter(os.Stdout)
n,m int
x,y,z int
// 边和节点数量级一样,说明是一个稀疏图,用邻接表存储更高效
h [N]int // 邻接表,表头
e [M]int // 邻接表 元素
ne [M]int // 邻接表,链表
w [M]int // 链接表 , 点点距离
idx = 0 // 邻接表索引
dist [N]int // 节点距离存储
queue []int // 队列, 宽度搜素存放待处理节点,只有距离变短的节点才需要重新计算一遍
st [N]bool // 是否已在队列中
cnt [N]int // 存储经过了多少个边
)
// 加入邻接表, 将 挂到 a 的 关系 链表中
func insert(a,b,c int){
idx++
e[idx] = b
ne[idx] = h[a]
h[a] = idx
w[idx] = c
}
// spfa 是对 bellman-ford 的一个优化
// bellman-ford每次循环要计算所有的点, 但实际上很多点不用重复计算
// 只有但一个点的距离变小了,其关联的点才需要更新
func spfa() bool{
// 开始节点的距离为0
// 不用初始化dist
// 因为是求是否存在负环,负环是会让dist减小,所以遇到负环必然会满足循环中判断dist是否减小的条件
// dist[1] = 0
// for i:=2;i<=n;i++{
// dist[i] = Max
// }
queue = make([]int, n)
copy(queue, e[1:n+1])
// 宽搜
for len(queue) > 0{
t:= queue[0]
queue = queue[1:]
st[t] = false // t 未在队列了
for i:=h[t]; i > 0 ; i=ne[i] {
x:=e[i]
if dist[x] > dist[t] + w[i] {
dist[x] = dist[t] + w[i]
cnt[x] = cnt[t] + 1
// 经过的边数大于等于n,表明存在环
// 为什么一定是负环呢?
// 因为正环实际上会被忽略掉,只有上距离减小(边权为负)才会让节点加入queue中继续计算
if cnt[x] >=n {
return true
}
// 变化的点加入队列 重新计算其关联点
queue = append(queue,x)
st[x] = true
}
}
}
return false
}
func main(){
fmt.Fscan(reader, &n, &m)
for i:=0;i<m;i++{
fmt.Fscan(reader, &x,&y,&z)
insert(x,y,z)
}
if spfa() {
fmt.Println("Yes")
}else{
fmt.Println("No")
}
}