Блог пользователя giorgi_pkhaladze

why do we need Floyd-Warshalls algorithm?
Автор giorgi_pkhaladze, история, 14 месяцев назад, По-английски

Hello codeforces! so as we know Floyd–Warshals algorithm finds the shortest path between all pairs of vertices and Bellman-Ford finds the shortest path from one note to all and if number of vertices will be_V and number of edges E then if we will run bellman ford from all vertices except one it will take o((v-1)*v*e) and floyd warshall takes o(v*v*v) that is mostly more than o((v-1)*v*e) am I right? So why do we need floyd warshalls algorithm?

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
14 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Let, $$$n$$$ = no of nodes, $$$m$$$ = no of edges Finding all pair shortest path using belmenford takes $$$O(n^2m)$$$ but floyed warshal takes $$$O(n^3)$$$ time. floyed is very easy to write and code is short.

→ Ответить
»
14 месяцев назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

Floyd can be optimized to n^3/32

→ Ответить
»
14 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

What do you mean by $$$O(V^3)$$$ is mostly more than $$$O(V^2E)$$$?

What if $$$E\gg V$$$?

→ Ответить
»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's useful when E is much bigger than V

→ Ответить