graphs in PostgreSQL

Hello,

I'm trying to organize storage and processing of a graph (pretty spare,
100,000 vertices and 5,000,000 edges) with PostgreSQL.

I have two main problems:
- standart problem of finding all shortest paths between two given vertices;
- search thru vertices' properties with ordering by path lengths from
given vertix.

So, basically, I need to decide what additional data (some preprocessed
data about a graph or indexes) I need to store, how to store it, and how
maintain it when graph changes.

It seems that the second problem (ordering by path length) requires to
store all path lengths between all vertices pairs (roadmap), that is
very expensive to maintain.

I would appreciate any suggestions...

--
Sincerely,
Ivan Zolotukhin