Systems and methods for provisioning QoS paths with restoration in a network. In one embodiment, one system includes: (1) a primary path generator configured to identify a suitable primary path between source and destination nodes in a network, (2) an auxiliary graph generator, associated with the primary path generator, configured to construct a directed auxiliary graph from an undirected graph representing the network by reversing each link in a primary QoS path of the undirected graph and replacing each other link in the undirected graph by two directed links, (3) a walk identifier, associated with the auxiliary graph generator, configured to identify a walk in the auxiliary directed graph corresponding to a set of bridges in the network and (4) a bridge identifier, associated with the walk identifier, configured to identify a set of bridges in the network such that at least one link of the primary path is protected by a bridge.