Airlines for Malaysia, Singapore, and Australia

Have you looked at Google Flights or Kayak to see what your choices are? ( then book directly with the airline)

Emirates might. I know they serve Australia and New Zealand, so they might also stop in the other places you mentioned.

You will probably do better looking at the flights within Australia as a separate ticket to your flight from the US. From Alice Springs you should consider visiting Uluru which is an incredibly impressive massive monolithic rock that is of enormous cultural significance to Indigenous Australians. You can visit Uluru yourself with a hire car or pick up a tour. Be prepared for cold nights in the central desert in August. Qantas and Virgin (main domestic carriers in Australia) would both have flights from either Alice Springs or Uluru to Melbourne.

In terms of airlines flying to and from Australia there is a huge choice. As you are going via KL then look at Malaysia Airlines. United and Delta would also fly to Australia either under their own brand or as codeshare. Also consider the Japanese airlines as their ticket prices have been good in recent months - ANA and JAL. To get to Darwin don't rule out flights that connect through another Australian city like Perth, Adelaide or Brisbane. If you look at the Darwin airport arrivals the only direct option from Singapore is Qantas - see Darwin arrivals. Darwin is not a major international airport.

You haven't said what you want to do in Melbourne. If you have no specific reason to go to Melbourne then also consider Sydney as it may give you better return flight options. In either city you need a minimum of three days to really see very much, and you could easily spend a week in either. With such a short time for your overall itinerary it might make sense to eliminate one of the Asian destinations and would make sorting out the flights much easier.

There's also Skyscanner.

Dear Bill

On long haul flights. On air travel I favour Qantas as it is a full-service airline and safest there is. Am a shareholder and achieved lifetime status which flows into Oneworld. Then the gulf carriers. I do not fly on price.

Singapore is a favourite location and Changi is, outside Gulf carrier airports, in my opinion the best one on the planet. Obviously is the hub for its airline which is government owned. May explain why it is one of the world’s best.

Kuala Lumpa (KL), hub for Malaysian, also government owned. My knowledge of the airport is not recent, last century.
Two others in the region, Cathay Pacific and Thai are excellent long haul. Last flew in on them to/from Europe in 2018. Philippines, Japan, and the gulf carriers are also excellent, but may involve layovers for you and extra travel time. Also, Vietnam Air is becoming an important player. Kiwi flyer should be worth a look. I have no idea how any of these connect across the Pacific. May be able to help when you firm up on dates, destination.

Short regional flights. At present to fly from KL or Singapore to Darwin is via Bali, Denpasar. I could not do that and not stop in Bali for a week. Jetstar, Scoot, AirAsia etc. Websites show base fare and then you add options, seat selection, hold baggage, food etc. Probably you are familiar with this style of airline. Have not flown them. I expect that these and other regional carriers will add more flights as things improve and a few direct flights will show up. At one time only option for me from Perth and Melbourne to Bali was Jetstar. Good pilots and well-maintained planes. Basic in other areas. Not my preferred airline.

Brilliant time of year for the Ghan. I assume you are taking Darwin through to Adelaide. There has been plenty of rain in the last year or so. And predicted, more to come over summer. Desert vegetation and animal life should be at its best. Suggested to my wife we should consider taking the old Landrover out for a bush spin in the red centre. Out voted by rest of family in favour of Europe and Canada. Majority wins.

May be able to help a little further as you flesh out the skeleton with questions on specific locations.

Regards Ron

All good advice.

Yes we will be seeing ayers rock, etc from Alice Springs, Thats the entire point of going to the red center other than the train ride.
We have been to Australia one time and flew Qantas going and AA coming back. Never AA over again, and Qantas was fabulous.
I will check out the SkyScanner. For now I am just trying to figure out general flight connections and will then focus on details.
Thanks again...

We had a good experience a couple years ago flying roundtrip LA/Sydney on Virgin Australia. At the time their flat-bed upgrade was way less than Quantas. Overnighting in LA (from DC) broke up what is a very long trip.

Yes we will be seeing ayers rock, etc from Alice Springs

It hasn't been called Ayers Rock for quite some time. Its name is Uluru. If you call it Ayers Rock it is disrespectful to indigenous Australians who are the owners of Uluru.

You are aware that it's 5 hours by car from Alice to Uluru, right?
You might be better advised to ride the Ghan only as far as Alice Springs, do you visit to the Rock, then fly out from the airport there to your next destination. Would save a day riding the train thru the featureless desert.
The hotels around Uluru fill up quickly - ensure that you book well ahead to avoid disappointment.
As has been mentioned, Jetstar is usually the best (and certainly the cheapest) way to get around inside Australia once you've arrived in the country.

We just got back from Australia and flew LAX to Fiji on Fiji Airlines. We stayed in Fiji for 3 nights while we recovered from jet lag, then took Fiji Airlines to Melbourne. We were able to use our Alaska Airlines mileage, as Fiji Airlines is a partner with Alaska. Keep in mind that Melbourne will be quite cold in the winter (August), but Darwin/Alice Springs will be more comfortable than in the summer.