HW3 bonus - betweenness
In Q1 you are asked to implement max_betweenness, by a simple loop that calls find_betweenness for every node in the graph.
Students' questions raised my awareness to the fact that this is a highly inefficient solution: the same computations are done again and again, when Dijkstra's algorithm is called for every source node many times. Such a solution, as you figured out, takes hours to terminate (it tool some 10 hours for some students).
A more efficient solution, that calls Dijkstra only once for every node takes on my computer less than a minute (!). You will get 5 bonus points for implementing such a solution.
Cheers,
Amir
