I think you're going about this the wrong way. Maximal path in a graph with cycles is technically undefined because it's infinite if the cycle lies between the start and end. There are probably clever ways you can extend/restrict the definition of maximal path, but I don't think that's the best approach here.
You're not trying to model an actual long path (e.g. a robot trying to explore as much area in a map as possible). You're just trying to get the player to explore many rooms.
So, make the chance the player finds the exit proportional to the percentage of the map explored so far. Let's say there's X rooms on a level, and the player character has explored Y. Next time the character enters a room, place the exit there with f(Y, X) probability. A trivial example of f might be (Y*Y)/(X*X) - e.g. for 10 rooms, there's a 100% chance the exit in the last room, 81% chance it's in the next to last room - and only a 1% chance it's in the first room.
You can tweak the equation however you want to make the game feel right, and maybe even give the player some abilities to make it more likely to generate. The key part is, don't generate the exit until the character actually enters the room. This method is also immune to player knowledge of the dungeon generation algorithm; even if the player has strange movement patterns like the knight's jump in NetHack or teleportation, they're going to have to explore more rooms to find the exit.
If you must statically generate the exit, you can use the same idea with a virtual character. Imagine a flood fill starting from the character's position, moving once cell each iteration. The last room to be filled is the room where the exit belongs (in fact, the last cell to be filled is the cell where it's farthest from the player). However, in this case the player has more information about the exit - if they're on the left, it's most likely on the right - and if they can teleport, may actually be able to get there faster than a normal random walk.
Finally, I just finished a roguelike where the exit spawned on the other side of the map from the player character, and then wandered randomly. Some items in the dungeon made it visible on the map, at the expense of getting hungry faster. I didn't do any analysis, but it definitely felt like I had to explore more of the map to find it, and it gave the levels a unique feel.