I believe you're using the wrong approach here by using shortestPath(), explanation below:
Be aware that when you use shortestPath(), it will MATCH for both start and end node variables according to your predicates, then attempt to find the shortest path for the resulting rows.
So this is not starting from U1 and expanding until it finds users according to the path and predicate you specified.
Instead (and you can see this in your PROFILE plan), it is performing an index lookup for U1, then using an IndexSeekByRange to get all :User nodes with an id <= max user id, and there are 100,000 of them. Then for each and every of those 100,000 pairs of nodes, it will execute a separate shortestPath() expansions to get the shortest path for the pair on that row.
If that is not what you want to do, then do not use shortestPath() for this. ShortestPath is for when you already know the start and end nodes and want the path between. You should not use it when you do not already know both the start and end node.