Résumé
In this paper we study two classes of graphs of shortest paths (GSPs), either increasing GSPs or general GSPs. These families of graphs are specific subclasses of directed acyclic graphs. Given an arbitrary graph and a fixed source vertex, a GSP is the subgraph containing all shortest paths originating from that vertex. For large GSPs, we provide a first-order asymptotic enumeration and use it to precisely describe their typical shape. Furthermore, our findings unveil significant connections and new results for bipartite graphs and triangle-free graphs. In particular, while upper bounds are already known for these graph classes we propose a lower bound for counting the graphs such that the node 0 has eccentricity equal to 3 and consequently to an exact asymptotic equivalent for these classes. We also deduce a linear rejection-based uniform sampler for both increasing and general GSPs, especially as the size of the GSP grows to infinity, the average rejection rate tends to 0.