## ← All Pairs Shortest Paths - Intro to Algorithms

• 3 Followers
• 20 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=HC46_DxEZjA" data-team="udacity"></div> ``` 3 Languages

Showing Revision 3 created 05/25/2016 by Udacity Robot.

1. As we discussed in the previous Unit, to find the most central node in a social network,
2. it's useful to be able to take each node in a graph and find out how far it is
3. from all the other nodes in the graph to get a square for a particular node and then to repeat
4. that operation essentially to find out the distance from every other node to every other node.
5. Really what we want to know is the shortest distance between any pair of nodes.
6. So all pairs we would like to know the distance--the length of the shortest path.
7. Now, given that we can execute a shortest path from any given node, then m*logn time.
8. We can just repeat than algorithm, just one at a time for each node run Dijkstra--
9. here's a node run Dijkstra--here's a node run Dijkstra--so you repeat it for all the nodes.
10. So we get n the number of vertices times nlogn for the total time--
11. to get the distance between all pairs of nodes.
12. This quantity can have a range of values depending on how dense the connect to the graph is.
13. If the graph is connected but very sparse, m is the same as n--so we get nÂ˛logn.
14. If the graph is very densely connected, then the number of edges is roughly the square
15. of the number of vertices and so the running time, at least in terms
16. of the number of vertices, now becomes nÂłlog n.
17. Now, you can do a little bit better than this using the Fibonacci heap idea
18. that I was mentioning before but may be this is the best that you can do
19. in terms of practically implementable code.
20. This on the other hand now we can beat this.