The replacement scheme will see a combined heavy rail and tram solution encompass a new section of railway known as the Dalmeny Chord, a new rail station and tram stop at Gogar on the Fife line.
The public will have access to the airport by tram from both Gogar and Edinburgh Park station.
The rail scheme will form part of an ambitious electrification plan for railways in central Scotland, based on the Edinburgh to Glasgow main line.
"I believe we need a step change between our two great cities," Scottish transport minister Stewart Stevenson told parliament. "So, we will electrify the route and connect lines to Alloa, Dunblane and Cumbernauld," Stevenson added.
"This will allow us up to six trains an hour between Glasgow Queen Street and Edinburgh Waverley, which can include non-stop services with journey times of 35 minutes," he added.
The electrification and connection to Edinburgh Airport formed part of ministers’ High Level Output Specification Tier 3 proposals.
An initial response from the Office or Rail Regulation (ORR) is expected on 20 October. The Scottish government has now determined that it is a top priority in their transport investment programme.
Stevenson said he expected the Edinburgh Airport connection elements to be completed by early 2011 to mesh with the opening of the Tramway. The Dalmeny Chord will allow some Glasgow to Edinburgh trains to call at Gogar.
"We have established that the difficulties in the EARL scheme highlighted in the auditor general’s report in June are not capable of resolution, and it is not safe to proceed with it," he said.
"Neither the BAA or Network Rail are prepared to project manage or construct the tunnel under the runway."
But opposition parties this week remained skeptical about the plan. "We don’t know about the deliverability, " Labour transport spokesperson Iain Gray told NCE after the vote.
"Until 27 June, the government was opposed to the tram scheme, so there cannot have been much work done on this," Gray added. "My suspicion is it won’t deliver much modal shift in journeys to the airport."
The eastern end of the Glasgow to Edinburgh route will be electrified, as part of the current Waverley Station and Airdrie-Bathgate schemes.
"This will be a 10-year staged programme of work and we will phase the construction packages to minimise disruption," said Stevenson.