At the start of The Fellowship of the Ring he seems to go from Shire to Minas Tirith to Saruman while the rest haven't traversed that much. How is this possible?
He doesn't. It's a movie inconsistency. It would have been very confusing for an audience who had never read the books to see a "17 years later" subtitle after that scene, with Frodo still the same age as before.
In the books
Gandalf doesn't directly travel to Minas Tirith after visiting Frodo. He only does so 17 years later after Bilbo's farewell feast. Gandalf only travels to Minas Tirith after he forsakes his chase for Gollum.
'With that thought, I forsook the chase, and passed swiftly to Gondor. In former days the members of my order had been well received there, but Saruman most of all. Often he had been for long the guest of the Lords of the City. Less welcome did the Lord Denethor show me then than of old, and grudgingly he permitted me to search among his hoarded scrolls and books.'
From the Timeline of Arda:
3001 Bilbo's farewell feast. Gandalf suspects his ring to be the One Ring. The guard on the Shire is doubled. Gandalf seeks for news of Gollum and calls on the help of Aragorn.
3002 Bilbo becomes a guest of Elrond, and settles in Rivendell.
3004 Gandalf visits Frodo in the Shire, and does so at intervals during the next four years.
3008 In the autumn Gandalf pays his last visit to Frodo.
3009 Gandalf and Aragorn renew their hunt for Gollum at intervals during the next eight years, searching in the vales of Anduin, Mirkwood, and Rhovanion to the confines of Mordor. At some time during these years Gollum himself ventured into Mordor, and was captured by Sauron. Elrond sends for Arwen, and she returns to Imladris; the Mountains and all lands eastward are becoming dangerous.
3017 Gollum is released from Mordor. He is taken by Aragorn in the Dead Marshes, and brought to Thranduil in Mirkwood. Gandalf visits Minas Tirith and reads the scroll of Isildur.