Существует несколько универсальных алгоритмов кратчайших путей для ориентированных графов с неотрицательными циклами, Флойд-Варшалл, пожалуй, самый известный, но с цифрами, которые вы привели, я думаю, что в любом случае у вас будут проблемы с памятью (время может быть проблемой, но вы можете найти универсальный алгоритм, который можно легко и массово распараллелить).
Независимо от используемого вами алгоритма, вам придется где-то хранить результат.А при хранении 20 000 000 ² = 400 000 000 000 000 длин путей (если не самих полных путей) будут использоваться как минимум сотни терабайт.
Доступ к любому из этих результатов, вероятно, будет более длительным, чем вычисление одного кратчайшего пути (стены памяти), которыйэто можно сделать менее чем за миллисекунду (в зависимости от структуры графа вы можете найти методы, которые намного, намного быстрее, чем Дейкстра или любой алгоритм, основанный на очереди приоритетов).
Я думаю, вы должны искать альтернативу, где не требуется вычисление кратчайших путей для всех, чтобы быть честным.Или, чтобы изучить структуру вашего графа (DAG, хорошо структурированный граф, легко разбить / кластеризовать, геометрическую / географическую информацию ...), чтобы применять разные алгоритмы, потому что в общем случае я не вижу никакого пути вокруг.
Например, с данными, которые вы дали, средняя степень около 5 составляет прилично разреженный график, учитывая его размеры.Тогда подходы к разбиению графиков могут быть очень полезны.