giorgi_pkhaladze's blog

why do we need Floyd-Warshalls algorithm?
By giorgi_pkhaladze, history, 8 months ago, In English

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?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
8 months ago, # |
  Vote: I like it -36 Vote: I do not like it

Floyd can be optimized to n^3/32

→ Reply
»
8 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes that why I said mostly and I think that bellman ford takes o((v-1)*v*e)

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      So then in these cases where $$$E\gg V$$$, the Floyd-Warshall will be much faster, so that's why it's useful

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's useful when E is much bigger than V

→ Reply