From the toolbox use the "Densify Geometries Given An Interval" tool and specify how far apart in map coordinates you want your extra vertices:
Note that my lines aren't exact multiples of the distance so you get some closer points (see bottom right).
The other "Densify Geometries" tool adds a fixed number of verts regardless of the length of the line feature. So, for example, each line gets 10 new points between its vertices, even if its a 10m line or a 1000m line.
Hopefully one of these will do you.
Actually hmmm - your lines already have more points than just the vertices and your graph is not showing them as nodes - its deleting all order-2 graph nodes and only keeping order-3 (and order-1) nodes. You may have to split each line into features at the nodes. You can do this with the "Explode Lines" tool.
If, after that, your graph still has no order-2 nodes then you'll need a different approach, which might be to snap your source point to the line geometry, do the routing by the nodes of the segment its snapped to, and then interpolate along the line segment.