﻿[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:00.00,0:00:05.00,Default,,0000,0000,0000,,As we discussed in the previous Unit, to find the most central node in a social network, Dialogue: 0,0:00:05.00,0:00:09.00,Default,,0000,0000,0000,,it's useful to be able to take each node in a graph and find out how far it is Dialogue: 0,0:00:09.00,0:00:12.00,Default,,0000,0000,0000,,from all the other nodes in the graph to get a square for a particular node and then to repeat Dialogue: 0,0:00:12.00,0:00:17.00,Default,,0000,0000,0000,,that operation essentially to find out the distance from every other node to every other node. Dialogue: 0,0:00:17.00,0:00:22.00,Default,,0000,0000,0000,,Really what we want to know is the shortest distance between any pair of nodes. Dialogue: 0,0:00:22.00,0:00:27.00,Default,,0000,0000,0000,,So all pairs we would like to know the distance--the length of the shortest path. Dialogue: 0,0:00:27.00,0:00:32.00,Default,,0000,0000,0000,,Now, given that we can execute a shortest path from any given node, then m*logn time. Dialogue: 0,0:00:32.00,0:00:36.00,Default,,0000,0000,0000,,We can just repeat than algorithm, just one at a time for each node run Dijkstra-- Dialogue: 0,0:00:36.00,0:00:40.00,Default,,0000,0000,0000,,here's a node run Dijkstra--here's a node run Dijkstra--so you repeat it for all the nodes. Dialogue: 0,0:00:40.00,0:00:44.00,Default,,0000,0000,0000,,So we get n the number of vertices times nlogn for the total time-- Dialogue: 0,0:00:44.00,0:00:46.00,Default,,0000,0000,0000,,to get the distance between all pairs of nodes. Dialogue: 0,0:00:46.00,0:00:51.00,Default,,0000,0000,0000,,This quantity can have a range of values depending on how dense the connect to the graph is. Dialogue: 0,0:00:51.00,0:00:57.00,Default,,0000,0000,0000,,If the graph is connected but very sparse, m is the same as n--so we get nÂ˛logn. Dialogue: 0,0:00:57.00,0:01:02.00,Default,,0000,0000,0000,,If the graph is very densely connected, then the number of edges is roughly the square Dialogue: 0,0:01:02.00,0:01:05.00,Default,,0000,0000,0000,,of the number of vertices and so the running time, at least in terms Dialogue: 0,0:01:05.00,0:01:09.00,Default,,0000,0000,0000,,of the number of vertices, now becomes nÂłlog n. Dialogue: 0,0:01:09.00,0:01:12.00,Default,,0000,0000,0000,,Now, you can do a little bit better than this using the Fibonacci heap idea Dialogue: 0,0:01:12.00,0:01:16.00,Default,,0000,0000,0000,,that I was mentioning before but may be this is the best that you can do Dialogue: 0,0:01:16.00,0:01:18.00,Default,,0000,0000,0000,,in terms of practically implementable code. Dialogue: 0,0:01:18.00,0:01:20.00,Default,,0000,0000,0000,,This on the other hand now we can beat this.