Большие тестовые случаи с графами на C++ (с использованием STL) выдают std::bad_alloc

Мы работаем над реализацией алгоритма графа (хранящегося как реализация списка смежности), который требует от нас сохранения следующего:

1. Двумерная n в n матрица расстояний (хранится в виде массива с плавающей запятой)
2. Количество кратчайших путей между каждой парой вершин (хранится в виде массива целых чисел).
3. Предшественники для каждой вершины, принимающей данную вершину в качестве исходной, для всех возможных вариантов исходной. Это O (n * n * k), где k - среднее количество предшественников для всех вершин по всем возможным выборам исходной вершины. В худшем случае это может быть пространство до O (n ^ 3). Однако среднее количество предшественников, вероятно, будет небольшим (k — константа). Предшественник хранится в виде двухуровневой карты, а список предшественников хранится в виде вектора STL.

Мы пробовали тестировать на больших графах (> 2 ^ 12 вершин), и это выдает std::bad_alloc после запуска в течение некоторого времени. Это происходит даже при работе на 8 ГБ (Ubuntu 12.04) или 16 ГБ с использованием только 3 ГБ памяти. Не могли бы вы рассказать, как мы можем заставить работать большие тестовые случаи, или мы где-то ошибаемся?