{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.manongdao.com/data/attach/logo/logo.png', '推荐 Root（大扎） 的问题《Can we apply the Bellman-Ford algorithm to an Undi》','https://www.manongdao.com/q-560112.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
I know that Bellman-Ford Algorithm works for directed graphs. Will it will work for an undirected graph? It seems that with an undirected graph, it will not be able to detect cycles because parallel edges will be considered cycles. Is this true or not? Can the algorithm be applied?
相关问题
- Finding k smallest elements in a min heap - worst-
- binary search tree path list
- High cost encryption but less cost decryption
- C++ a class with an array of structs, without know
- How to get a fixed number of evenly spaced points
相关文章
- Mercurial Commit Charts / Graphs [closed]
- What are the problems associated to Best First Sea
- Coin change DP solution to keep track of coins
- Algorithm for partially filling a polygonal mesh
- Robust polygon normal calculation
- Algorithm for maximizing coverage of rectangular a
- Is there an existing solution for these particular
- Systematically applying a function to all fields o
Bellman-Ford is not applicable to find shortest paths on graphs which contain negative cycles, but it finds shortest paths on graphs and can detect if the graph contains a negative cycle, although it won't find a shortest path, as no such path exists.
As a matter of fact any undirected graph is also a directed graph.
You just have to specify any edges {u, v} twice (u, v) and (v, u).
But don't forget, that this also means any edge with a negative weight will count as a loop. As the Bellman-Ford algorithm ONLY works on graphs that don't contain any cycles with negative weights this actually means your un-directed graph mustn't contain any edges with negative weight.
If it doesn't its pretty fine to use Bellmann-Ford.