anu*_*han 10 algorithm graph graph-algorithm data-structures bellman-ford
我知道Bellman-Ford算法适用于有向图.它是否适用于无向图？似乎使用无向图,它将无法检测周期,因为并行边将被视为周期.这是真的吗？算法可以应用吗？
mik*_*yra 31
事实上,任何无向图也是有向图.
您只需要指定任何边{u,v}两次(u,v)和(v,u).
但不要忘记,这也意味着任何具有负重量的边将被视为循环.由于Bellman-Ford算法仅适用于不包含任何具有负权重的循环的图形,这实际上意味着您的非定向图形不得包含任何具有负权重的边缘.
如果使用Bellmann-Ford不是很好的话.