Welcome
First two general remarks: a) in essence it doesn't matter much whether you start and finish in Prague or Budapest, so just see what is cheaper - flight your city-Prague or your city-Budapest; b) within triangle Budapest-Vienna-Bratislava overnight journey isn't an option, distances between the cities aren't lengthy enough.
Since you mentioned Prague first, let's look at the itinerary starting & ending in Czech Republic:
Prague to Krakow: there is an overnight direct carriages (discounted tickets for seats start from only 19 euro, couchettes from 29 euro, sleepers from 39 euro). And the great thing is that Czech railways sell this discounted tickets in advance via
eShop (ticket sale starts 60 days in advance)
Krakow to Budapest: here we stumble with the most essential problem - Polish railways doesn't sell tickets to Budapest (or Vienna, or Bratislava) online, so cheap discounted tickets can be bought only in Poland at the counter or via resellers (=extra commission). Alternatively easiest and cheapest option here would be to rely on bus connection -
Hungarian Eurolines 4 times a week runs an afternoon bus from Krakow to Budapest and best thing is that tickets for the connection start from only 3900 HUF (app.12 euro) + can be purchased online. Sure bus ride here won't be as convenient as train, and it's not an overnight one, but bus ticket price says much more, because for the train on the day of departure you'll have to pay 85 euro (+ potential sleeper reservation fare).
Budapest to Vienna: probably easiest leg - many trains, discounted one-way tickets start from only 13 euro and can be purchased via Hungarian railways (MAV) website (we even have a step by step guide on how to do it -
http://europetrainsguide.com/Advice/How-to-Buy-Train-Tickets/Hungary-MAV.html )
Vienna-(Bratisalva)-Prague: you can get an overnight train from Vienna to Prague, but it's a bit expensive (sleepers from 59 euro, however seats on daytime trains start from only 29 euro), so cheaper would be to travel to Bratislava and from there catch a train to Prague. To do so you first need to travel from Vienna to Bratislava, takes roughly an hour (by train it would cost you 15 euro, while by bus 7,7 euro). While from Bratislava you can easily get to Prague for as low as 15 euro (discounted tickets purchased via
Slovak Railways website). Also available overnight option.
Also possible to do a reverse itinerary: Prague-(Bratislava)-Vienna-Budapest-Krakow-Prague (websites for ticket purchase and schedules are the same, but again it will be necessary to do some tricks for Krakow-Prague leg, because Poles don't sell discounted ticket online, while paying full price kind of too much)
Anyways, we advise you to check out websites and options mentioned above, see everything yourself and then we would be glad to answer any additional question you might have
Author