Floyd Warshall Graph Traversal Algorithm: All-pairs Shortest-paths

[@kunafeh]

The music in the beginning had me feel like an action movie is about to begin.

[@mariaa.furfaro3614]

it is kind of... disturbing

[@lenlen8099]

It's from Beethoven Virus

[@bablobko]

Everytime I watch these videos, I start liking Algorithms more and more.

[@bablobko]

You're the Master of Algorithms James. Bows to you.

[@ThePolochon92]

Best explanation of this algorithm I've seen ! Thx

[@roltthehunter]

I am doing a problem from UVa Online Judge and this really really helped. It was part of my extra credit for a class i am in. Thanks a lot for this video.

[@joejamesusa]

+roltthehunter oh good! Glad it helped you.

[@RusseltheViper]

OH man you are a life savior,thanks for the video!

[@dayas1234]

Thank you so muchSir; for presenting these tough algorithms in a easy way to learn.

[@srinivasmaheedhar4118]

Very well explained @Joe James, awesome job!! I liked all the videos of yours watched so far! Thank you!

[@joejamesusa]

+Srinivas Maheedhar thanks.

[@ΔημήτριοςΙντζελερ]

You forgot to make some changes during iterations but you explained it so well I understood the algorithm in no time. Thank you very much

[@leoniduvarov6565]

This is an incredible explanation!

[@NikkieBiteMe]

Great one. The intro was splendid too.

[@josemunguia5660]

Best explanation ever! Thank you Mr.James!

[@molan011]

Very good explanation of an example :)

[@ashishjoshi2920]

Thanks joe for the perfect explanation..!

[@parasite34]

Thanks Joe James!

[@madawacko258]

Very good explanation, Thank you!

[@ramasubramanyam5676]

Very nice explanation and presentation of the algorithm. Thank you very much for the same.

[@NarendrakumarSoni]

It was beautifully explained. Thank you so much.

[@firuzibragimov4521]

Simple and clear. Thank you!

[@joyhanzes7537]

Great explanation :) I really like the way you use to explain. I can understand easier than in my class room. lol

[@ayusumardi]

Your video is easy to understand. thank you so sir.

[@ericg2920]

props for the clear explanation!

[@jigneshdarji9104]

Thank you so much, Joe

[@Ms_Oszy]

This the best explaining ever.. Thanks :):):)

[@sasidharannarasimhan5861]

thank you so much helped me a lot during exam..explanation was very clear and concise

[@doge-coin]

Clear explanation! Thank you so much!

[@mustafamehmetbayar3594]

thanks Mr.James, you've made everything crystal clear =')

[@a1ecu]

Nice explanation and very helpful video!

[@skeltor575]

Thanks so much for the great breakdown!

[@abhishekratnawat4708]

amazing explanation... best for the topic

[@mdmushfiqulislam5391]

Thanks for the video.

[@ThePotentialCrisis]

Great video! Helped a bunch!

[@danieldawson9266]

Awesome vid, nice explanation

[@krishnadaskp9683]

Just Brilliant.

[@armanjabbari2416]

Great tutorial, thanks

[@harshkothari6035]

I think you forgot to highlight in d4 and pi4 that the distance from A to B and its predecessor also change. A great explanation btw :)

[@joejamesusa]

+Harsh Kothari oh, you're right! Sorry. The d4 and pi4 tables are all correct, except I should have highlighted the B-A square because it changed to 4D.

[@卉-s4q]

Best explanation!! Thx~

[@joejamesusa]

+史卉 谢谢

[@carolw3391]

+Joe James Nice Chinese~ :D

[@SinghLalit]

This is the best explanation I have found over internet!!!

[@ankitthehot]

Nice explanation!!!

[@surajdidwania8692]

Good Explanation!!

[@PomegranateAmazing79]

You should have added the method of tracing back the path between a pair of vertices.

[@xiaoranlr]

Great tutorial!

[@parichaypapnoi5406]

thanks man..good explanation

[@1996harith]

Awesome man. Just awesome

[@YouB3anz]

very nice

this is awesome, thanks

[@idobooks909]

Thanks to the intro it feels like an action movie :) Yay! One small thing: A --> C is marked in the Pi(i) as "A" whereas A --> D is marked NULL and I think it should be marked "A" as well :) Will you put a notation there for the generations to come? Thanks!

[@istvanszabo6875]

great job sir

[@kashifahmadin7164]

around 7:10 ~ 7 : 15, we are trying to get from D to A via B, you highlight the wrong weight of -2 of B to D whereas it should be B to A. Please do correct me if im wrong

[@joejamesusa]

Oh yes, I highlighted the wrong square, but the result is the same since B-A and B-D are both -2.

[@aainagoyal4065]

it was v good and v clear

[@Mark-du9rv]

saved lot of time!!!

[@het314]

Best one.

Thank you!

[@nimamaleki1595]

Beautifully explained! Is it true that if we have an update on the diagonal of d1,d2,d3... we should halt, because that is a negative cycle?

[@joejamesusa]

+Nima Maleki yes, that is true. A negative distance from any vertex to itself would indicate a negative cycle, which the algorithm does not support. So if you are applying Floyd-Warshall's to a graph that COULD contain negative cycles you could implement a check in the algorithm that halts if it finds a negative weight from any vertex to itself.

[@nimamaleki1595]

+Joe James Thank You so much!

[@Zlappyzopstix]

Nice one cheers

[@UCHS_CH]

A---c = A; all right but A---D = 0 ,in parent table is missing? why *1:34

[@FarhaJawedCSE_MIST]

Thanks a lot :) That helped!

[@gamerorange]

For the D3 table, there should be the value 12 for A-B, right ? Since you can do A > C > D > B ?

[@joejamesusa]

+gamerorange no, why would you do that when you could do A > D > B at a total cost of 4?

[@gamerorange]

+Joe James yes you are right. So why is it infinite in the d3 table for AB. Shouldn't it be 4 ?

[@joejamesusa]

+gamerorange no because we don't consider paths through vertex D until the 4th iteration, table d4.

[@Omar-rc4li]

More useful than all the music videos getting more than billion views.

[@poojanshah998]

In third iteration isn't there a path from A to B through C(distance of 12)?

[@bgpeters22]

Why is there not an A in the A-D coordinate of the pi0 matrix? Is it cause the distance is 0?

[@joejamesusa]

+bgpeters22 you're right, there should be an A in that box of the pi0 table. d0 and pi0 should reflect all direct edges from one vertex to another.

[@ordinarycoder8090]

Nice video

[@agamsinghbajaj256]

In table d4, although the value is updated for A-B path, you mention only C-A and C-B are the changes. I do see A-B in bold so maybe it was an error while creating the slide. Am I right in saying A-B path is updated while going through D? A-D : 0, D-B: 4, A-D in d3 =+inf, therefore update A-B to 0+4=4.

[@joejamesusa]

+Agam Singh Bajaj yes, you are right. My table is correct, but I should have bolded that square and mentioned that it changed in the 4th iteration.

[@agamsinghbajaj256]

+Joe James Thumbs up for the explanation though. :)

[@fathiak6068]

can i have this information on a pdf or word can u send it to me ??

[@joejamesusa]

most of my power point files are online here, github.com/joeyajames/UsefulUtensils

[@fathiak6068]

thank u

[@mysmallcap]

Thank You :)

[@Alexic94]

I had a question to find "eccentrics of all nodes" and a "center" of the graph after using Floyd-warshalls algorithm, is there something like that?

[@joejamesusa]

+Alexic94 Floyd Warshall's cannot compute a center or centroids for a graph. You could use the distances calculated by Floyds, and write your own algorithm to compute a center. Better still, there are clustering modules in R that could easily do that if you have an existing data set. I believe they use K-Means, which you could read up on if you want to learn how it works.

[@Alexic94]

+Joe James According to my professor for the center of the graph you take the last table you made, for example D4 and look at the highest number in each column, ex. 1:17, 2:12, 3:12, 4:6,5:15....And since the node 4 has the highest value of 6 and the lowest value of all the other nodes, node 4 is the center of the graph. I dont quite understand it either and im afraid to question his methods :)

[@akhilanatarajan7647]

can you explain why we have -2 for B to D in table d2 as against 1?

[@Andreas_Mann]

+aks car B - > A = -2 and A - > C = 0 - 2 + 0 = - 2

[@akhilanatarajan7647]

+nirvanahater thnku

[@석상주]

I understand everything except the setting up the predecessor. Your predecessor table makes sense if # of intermediate nodes is at most 1. In this example, this is true for all paths. But how do we keep track of all intermediate nodes with there's more than 1?

[@joejamesusa]

+석상주 when the algorithm is done you can trace any path using the predecessor table, even for large graphs. Just continue looking at the predecessor's predecessor until you reach the source node.

[@2358vishu]

Correct me if I am wrong, the predecessor of edge CA should be 'B'.

[@joejamesusa]

+Vishal Panwar you bring up a good question that I didn't really cover in the video. How do we retrace the path from node i to node j? Since I actually stored in pi the successor to i, you would have to continue following the successor nodes until you reach node j. So that's one way to do it, using pi to store the next node from i. OR, you could store in pi the predecessor to j. You could also reconstruct the path this way by getting j's predecessor until you reach i. Both ways will work. However, you're right, I stored the next node in pi and I called it the predecessor, which is not true. So in this video D-C and C-A both have NEXT nodes stored in pi rather than PREDECESSOR nodes. Sorry for the confusion, but I don't think I'll correct it because if I were coding it I would actually save the next value rather than predecessor. One of the main applications of shortest path algorithms is routing, and routers only need to know the next hop, so it makes most sense for pi to store the next node rather than predecessor.

[@mintsponge]

jesse eisenberg?

[@malharjajoo7393]

Sorry but you have not justified the harder part of the explanation. Can you explain how the steps lead to your intuition ( from 0:46 ).

[@MegaRyad]

gi joe

[@radulescuiulia8988]

Great explanation! Thanks!

[@mohammedashkiwala4153]

THANK YOU!