Algorithm for finding subgraphs?

Question

Algorithms

There is an undirected graph with a million vertices and 100 million edges. Each edge has its own weight. The task is next. Two vertices are given. It is necessary to find all paths between two vertices, consisting of 4 edges, and the paths must be sorted in order of increasing / decreasing the total weight of the path.
Also, I will be grateful for the link, since I have already exhausted myself to look for sensible information on the graphs. Thank you.

Answer 1

Depth-first search with depth limit = 4.
Having reached depth = 4, add to the sorted list. Is it simple?

Answer 2

If everything is symmetrical, then the most reasonable option is breadth-first search (this is what is called a wave) from 2 sides, 2 steps from each. In total there will be two lists of 100 ^ 2 vertices in which you need to find intersections and sort them. Taking into account the fact that the received paths will almost always be less than 10,000, it probably makes no sense to take a steam bath, you can safely shove everything into a heap and go through quick sorting (although it depends on the system, if this place takes up a significant part of the resources, then you can probably come up with something better ).
And - this option is about 100 ^ 2 / 2 times faster than searching from one vertex. With a little thought, a computationally simple task can easily be turned into a resource-intensive monster :)

Answer 3

In principle, TheHorse said everything correctly. True, from the point of view of terminology, it is more correct to say (IMHO) that it is necessary to implement the wave front algorithm from one point to another, although in essence it is the same thing. True, I mistyped the numbers a bit: 100^4= 100,000,000.