우리는 Bellman ford 알고리즘을 Undirected Graph에 적용 할 수 있습니까

Bellman-Ford 알고리즘은 유향 그래프에서 작동하지만 정보에서는 Un-directed 그래프에서 작동하는지 여부를 알고 싶습니다. Un-directed 그래프에서는 병렬 에지가 Cycles로 간주되므로 사이클을 감지 할 수 없습니다! 명확히하십시오.우리는 Bellman ford 알고리즘을 Undirected Graph에 적용 할 수 있습니까

출처

2013-02-09 anuj pradhan

[this] (http://stackoverflow.com/questions/14538403/shortest-path-algorithms-for-undirected-graph) 하나보십시오. – Nik

실제로 모든 무향 그래프는 유향 그래프이기도합니다.

가장자리 {u, v}를 두 번 (u, v) 및 (v, u)로 지정하면됩니다.

그러나 부정적인 가중치를 가진 모든 엣지가 루프로 계산된다는 것을 잊지 마십시오. Bellman-Ford 알고리즘은 음의 가중치가있는 사이클을 포함하지 않는 그래프에서만 작동하므로 실제로는 유향이없는 그래프에 음수가있는 모서리가 없어야합니다.

Bellmann-Ford를 사용하는 것이 꽤 괜찮 으면.

출처

2013-02-11 00:59:27 mikyra

이것에 대해 자세히 설명합니다 - 그래프가 음수가 아닌 에지 만 가져야하기 때문에 이것은 점근 적으로 빠르기 때문에 Dijkstra의 알고리즘을 대신 사용할 수 있습니다. – templatetypedef

나는 똑같은 의혹을 가지고있다. 설명해 주셔서 감사합니다. – whitehat

우리는 Bellman ford 알고리즘을 Undirected Graph에 적용 할 수 있습니까

답변

관련 문제