Routers balance network traffic among multiple paths through a network according to an amount of bandwidth that can be sent on an outgoing interface computed for each of the paths. For example, a router receives a link bandwidth for network links that are positioned between the first router and a second router of the network, and selects a plurality of forwarding paths from the first router to the second router. Upon determining that one of the network links is shared by multiple of the plurality of forwarding paths, the router computes a path bandwidth for each of the plurality of outgoing interfaces so as to account for splitting of link bandwidth of the shared network link across the multiple forwarding paths that share the network link. The router assigns packet flows to the forwarding paths based at least on the computed amount of bandwidth for each of the outgoing interfaces.