I am not sure about a simple way to do it in Qgis.
You have a tool called "explode lines" in Geotraitment toolbox,
this tool will return each segment of your lines and with some spatial query you can retrieve id for each segment.
There is maybe some plugins also that i am not aware of it.
But I could propose a rather good solution with the use of Postgres ...
I think the closest would be the LRS pluggin
Standard LRS tasks: calibration (creation of LRS), creation of punctual and linear events and calculation of measures for points.
Support for all vector formats supported by QGIS.
Supported are lines, multi-lines, points, multi-points. The lines don’t need to be oriented. Single route ...
I see this question had a little bit of activity recently, so I will post my eventual solution. It essentially follows the strategy of my last comment.
There are two types of nodes: those which define junctions between road segments (ie. a graph node); and intermediate nodes which define the shape of the road segment. These are dropped for routing, but I ...