Есть необходимость решать 2 задачи:
1) Находить на не взвешенном графе кратчайший путь, избегая заданных вершин, а если избежать их невозможно - с минимальным количеством таких вершин.
вершин около 7000, рёбер 14000

2) Находить кратчайший путь на графе между двумя точками, ребра которого имеют вес.
вершин 4000, а вот ребёр 2 миллиона

Хочется конечно делать это максимально быстро, а в теории графов и алгоритмах разбираться не хочется.
Какие есть модули, для работы с графами, способные мне помочь?
Нашел в инете достаточно, но всё же не совсем понятно, какие из них мне подойдут. Может кто-то использовал?

Далась вам эта серебрянная пуля…
Берите алгоритм Форда- и вперед

Я использовал networkx. Впечатления положительные. Но если бы эта задача стояла передо мной, то я бы просто протестировал все возможное. В том числе и свою реализацию.

Еще народ хвалит igraph. Он должен по идее быть быстрее - написан на С.
Вот тут тред про сравнение networkx и igraph: http://groups.google.com/group/networkx-discuss/browse_frm/thread/7597ca97abbb3f90?hl=en

Попробовал networkx, библиотека очень хорошая и простая, много алгоритмов есть.
Только вот мой второй граф в памяти занимал 500мб.
Поэтому сделал сам, через словари. В памяти занимает 170мб. Но всё равно много - база из которой импортируются рёбра весит 40мб. Как можно уменьшить количество занимаемой памяти?

igraph пробовали? Поскольку он на Си написан, то по идее хранить данные должен компактнее, чем Питон.
Покажите как Вы сделали через словари. Без кода очень трудно что-либо советовать.