From memory of a book read long ago, called, I think, The Navigators.

The term navvie is an abbreviation of navigator, from the labour force that dug the earlier form of mass transportation, the canals or 'navigations.'

Hard men, mighty workers, hearty eaters, and unpopular with the locals around where they were working, because of accusations of theft. The first navvies were English, although the term has now become almost exclusively linked with Irish.
When building the railways in India, English firms are supposed to have found it cheaper to import experienced navvies from Britain, the local labour being ineffective for such brutal work. The book said it was thought to be due to the local diet.