What are the libraries for fast graph search of shortest paths and independent closed loops in C++?

Question

Mathematics

In graduate school, by occupation, I had to deal with large graphs (1000-3000 vertices, 10,000 edges).
The graph is represented by an incidence matrix ( https://ru.wikipedia.org/wiki/Incident_Matrix ). I wrote the work with matrices and the graph in the prototype program myself. Now it's time to optimize individual sections. To work with linear algebra (matrix multiplication, solve, sparse matrices) I took Armadillo. And, lo and behold, I won in speed 20-50 times.
Then I set out to optimize the processing of the graph. The task sounds trivial.
Initial data: incidence matrix (highly sparse matrix);
Task:
1) get the shortest path from one node to any other as quickly as possible (the weights of all edges, for example, are equal)
2) get the matrix of independent contours of the graph as quickly as possible (independent - does not contain nested contours)
The tasks are quite typical. Perhaps there are already ready, fast, "high-quality" solutions in C++?

Answer 1

boost:: graph ?

Answer 2

3000 vertices and 10000 edges is a small graph.)
To solve matrices, I can also advise you to try taucs and mkl pardiso (you have to steal).
The already mentioned BGL can be screwed to find the shortest path. It doesn't matter how the graph is represented in memory, because you provide iterators to traverse the graph, but you have to fiddle around to program them. But you can try both depth-first search and breadth-first search. If you are not afraid of the word "recursion", then implement the search for A*. It will be both easier and faster (maybe) than boost.
Independent contours can be found using the head-on method. Create an additional structure with vertex number and contour number. Then you take any vertex and recursively mark all associated vertices with it. Then you start a new contour from any unmarked vertex. The complexity of the algorithm is linear.

Answer 3

Any library focused on working with graphs, of course, must also support basic graph traversal algorithms, and not in a naive, but in the most mathematically flawless execution. Therefore, any will suit you. Do not write this yourself.
When puzzled by graphs, I came to the conclusion that boost::graph is the best, although not perfect solution. But if you are heavily OOP oriented and generic programming is difficult, then it is better to look for an OOP oriented alternative.