giorgi_pkhaladze's blog

...
By giorgi_pkhaladze, history, 15 months ago, In English

...

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

Comments Comments (7)
| Write comment?
»
15 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
»
15 months ago, # |
  Vote: I like it -36 Vote: I do not like it

Floyd can be optimized to n^3/32

→ Reply
»
15 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
  • »
    »
    15 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
    • »
      »
      »
      15 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
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's useful when E is much bigger than V

→ Reply