You will certainly have as many records as there are paths if there is need to store them. No way around here.
If I understand correctly you seek for a design that prevents you from storing all vertices as a single attribute ('A,B,D') or a separate table.
In this case, take a hierarchical approach:
path_id segment_id next_vertex -- which path it represents
1 A
2 B
3 C
4 D
5 1 B -- A B
6 1 C -- A C
7 2 D -- B D
8 3 D -- C D
9 5 D -- A B D
10 6 D -- A C D
Here segment_id represents the subpath without last vertex. Now, for example, path 10 represents "A->C->D", which consists of "A->C" (path 6) with vertex D added at the end. You can traverse the hierarchy by going down the tree same way.
Note we also got here 'degenerate paths', containing just a single vertex, where segment_id is null.