I disagree that you have to have a 3D map for this, and depending on how far along you are and how you implemented things, it might be a lot of work or bring other problems if you try to convert your tile or map system from 2D to 3D. On the other hand, it might be appropriate for your game and even help you with other things, but that's hard to say without knowing your game and your plans very well.
If you want to stay in 2D, you'd have to implement some special logic depending on tile type. You could make certain tiles only passable in certain directions (e.g. not letting you turn left or right at this bridge/tunnel tile, or having one-way tiles that only let you pass in one direction - for example for dropping "down", like you could in older Zelda games). Your pathfinding then has to follow these rules when expanding the set of possible moves from the current tile.
The trickiest thing about this is probably the rendering, because you'd want to have elements on the bridge stay visible and those below should appear to be under the bridge. One approach would be to compose the tile of two seperate sprites, one floor and one bridge sprite, so that you can draw the bridge sprite after an object that's below the bridge, but before an object on the bridge.