More efficient vertex-labelling algorithm than BFS?
For graphs that fit into main memory (or even in a largish L3 cache), you probably can't do much better than your library's traversal algorithm without significant effort.

But anyway, you're way into "try and measure" territory. Robert Sedgewick has a nice talk Putting the Science back into Computer Science, that explores flow problems as an example. He uses Ford-Fulkerson, not push-relabel.