Is there a way in python to make a list with the minimum weight of each path between two data points without taking too much time?

Question

I need to do the following thing:

Given a fully connected graph I want to calculate the path similarity between each pair of vertices.

To do that for a pair ($i$, $j$) we need to take the the maximum value of the following set: {minimum edge weight for each path : where the path starts in $i$ and end in $j$.

Obviously it is possible to consider all paths between $i$ and $j$, take the minimum edge weight of each one, then take the maximum between these minimal edges weights, but this takes too long for a large graph. Does anyone know a way to do this more quickly?

Answer 1

The hardest part is to compute, for each pair of vertices $(i,j)$, the minimal weight of a path from $i$ to $j$. There is an effective way to do that : what you need is a good old Djikstra's algorithm.

Once you've got your function, say djikstra(i, j), that computes "minimum edge weight for each path : where the path starts in i and end in j", all you have to do is to take the maximum value thereof.
Say your vertices are indexed from 0 to n−1, you get the answer with (don't forget to import itertools) :

answer = max(djikstra(i, j) for (i, j) in itertools.product(range(n), range(n)))