$\newcommand{\defeq}{\mathrel{\mathop:}=}$

## 2007/04/05

### 有瑕

• Run Bellman-Ford to detect negative cycle in O(mn) time. If there are negative cycles, then stop.
• For each node i of the input graph G:
Run Bellman-Ford in O(mn) time to compute d(i, j) for all nodes j.
• The overall time complexity is O(mn2), which could be Θ(n4) in the worst case.

• For each node i of the input graph G:
Run Bellman-Ford in O(mn) time to compute d(i, j) for all nodes j. If a negative cycle is detected, then stop.

--

--

• The node weight function h can be obtained by Bellman-Ford in O(mn) time.

--

Labels:

yen34/05/2007 4:01 pm 說：