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.
+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.
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
+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.
+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 :)
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.
+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.
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?
+석상주 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.
+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.
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!
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
The music in the beginning had me feel like an action movie is about to begin.
it is kind of... disturbing
It's from Beethoven Virus
Everytime I watch these videos, I start liking Algorithms more and more.
You're the Master of Algorithms James.
Bows to you.
Best explanation of this algorithm I've seen ! Thx
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.
+roltthehunter oh good! Glad it helped you.
Very well explained @Joe James, awesome job!! I liked all the videos of yours watched so far! Thank you!
+Srinivas Maheedhar thanks.
Thank you so muchSir; for presenting these tough algorithms in a easy way to learn.
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
Very nice explanation and presentation of the algorithm. Thank you very much for the same.
Best explanation ever! Thank you Mr.James!
OH man you are a life savior,thanks for the video!
Great explanation :) I really like the way you use to explain. I can understand easier than in my class room. lol
thank you so much helped me a lot during exam..explanation was very clear and concise
It was beautifully explained. Thank you so much.
Great one.
The intro was splendid too.
Your video is easy to understand. thank you so sir.
Very good explanation of an example :)
Thanks joe for the perfect explanation..!
Very good explanation, Thank you!
Nice explanation and very helpful video!
This is an incredible explanation!
thanks Mr.James, you've made everything crystal clear =')
amazing explanation... best for the topic
Simple and clear. Thank you!
Clear explanation! Thank you so much!
Thanks Joe James!
Thanks so much for the great breakdown!
This the best explaining ever.. Thanks :):):)
props for the clear explanation!
Awesome vid, nice explanation
Great video! Helped a bunch!
This is the best explanation I have found over internet!!!
Thanks for the video.
Thank you so much, Joe
Nice explanation!!!
Great tutorial, thanks
Good Explanation!!
thanks man..good explanation
Great tutorial!
Best explanation!! Thx~
+史卉 谢谢
+Joe James Nice Chinese~ :D
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 :)
+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.
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
Oh yes, I highlighted the wrong square, but the result is the same since B-A and B-D are both -2.
great job sir
this is awesome, thanks
it was v good and v clear
very nice
Just Brilliant.
Awesome man. Just awesome
A---c = A; all right
but A---D = 0 ,in parent table is missing?
why
*1:34
saved lot of time!!!
For the D3 table, there should be the value 12 for A-B, right ? Since you can do A > C > D > B ?
+gamerorange no, why would you do that when you could do A > D > B at a total cost of 4?
+Joe James yes you are right. So why is it infinite in the d3 table for AB. Shouldn't it be 4 ?
+gamerorange no because we don't consider paths through vertex D until the 4th iteration, table d4.
In third iteration isn't there a path from A to B through C(distance of 12)?
Thanks a lot :) That helped!
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?
+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.
+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 :)
Nice one cheers
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.
+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.
+Joe James Thumbs up for the explanation though. :)
can you explain why we have -2 for B to D in table d2 as against 1?
+aks car B - > A = -2 and A - > C = 0
- 2 + 0 = - 2
+nirvanahater thnku
Correct me if I am wrong, the predecessor of edge CA should be 'B'.
+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.
Why is there not an A in the A-D coordinate of the pi0 matrix? Is it cause the distance is 0?
+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.
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?
+석상주 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.
Nice video
You should have added the method of tracing back the path between a pair of vertices.
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?
+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.
+Joe James Thank You so much!
Thank you!
Best one.
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!
can i have this information on a pdf or word can u send it to me ??
most of my power point files are online here, github.com/joeyajames/UsefulUtensils
thank u
More useful than all the music videos getting more than billion views.
Thank You :)
jesse eisenberg?
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 ).
gi joe
Great explanation!
Thanks!
THANK YOU!