You are not logged in. Please login at www.codechef.com to post your questions!

×

Floyd Warshall Algorithm

Could someone please give me a basic intuition between the Floyd Warshall algorithm like how you would explain it to a layman? In addition to when it is/isn't preferred over Dijakstra's algorithm?

I've tried looking up various sources but it's like, if I read a pseudocode I am able to understand what they are doing but not why they are doing it, which is pretty pointless as that is not the right way to learn.

Could someone please help me out?

asked 10 Jan '15, 20:45

sandy999's gravatar image

2★sandy999
39111538
accept rate: 10%


I think you are yet to watch the best tutorial for this alg. Plz check out https://www.youtube.com/watch?v=EMAoMMsA5Jg

It'd be better if you revise a bit of DP, cos its after all a DP alg.

All the best!!!

link

answered 10 Jan '15, 23:10

arpanb8's gravatar image

3★arpanb8
1201312
accept rate: 13%

edited 10 Jan '15, 23:11

This video was exactly what I needed! Thank you so much!

(11 Jan '15, 16:47) sandy9992★

@sandy999 acctually i was also hvin the same trouble...but this video made it all clear... Plz. find my code for FREETICKETS and help me locate the errors. u can find it in the disc. on FREETICKET.

(12 Jan '15, 00:31) arpanb83★

I think you forgot to include your code

(12 Jan '15, 00:44) superty3★

Check the discussion on FREETICKETS...I inserted it in 1 of d ans..

(12 Jan '15, 01:00) arpanb83★

Hi. I'm not a pro coder nor am I an expert on graph theory, but I wanted to share what I know. Essentially, Djikstra's Algorithm is used to find the shortest distance from a particular node to another given node (shortest as in, cheapest or lightest). On the other hand, Floyd-Warshall is used to find shortest costs of all-pairs of possible paths (refer to FREETICKET problem for an example/implementation).

Hope I could help a bit. Please ping back if you find anything confusing.

link

answered 10 Jan '15, 22:09

pm1511's gravatar image

1★pm1511
3156
accept rate: 0%

edited 10 Jan '15, 22:11

Hey thanks for your help :)

(11 Jan '15, 16:46) sandy9992★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×65

question asked: 10 Jan '15, 20:45

question was seen: 639 times

last updated: 12 Jan '15, 01:04

Related questions