There are many airlines that provide the direct flights to Johannesburg, and the top most out of them are Airlink (4Z) with 41 routes to JNB, CemAir (5Z) with 13 routes to JNB, British Airways (BA) with 10 routes to JNB, South African Airways (SA)8 routes to JNB, Safair (FA)6 routes to JNB. You should book your flight in a month of low demand to get a flight at reasonable prices. You may have to dig deeper in your research to look for the cheapest booking month. The advance booking of the flight is suggested even for your connecting flight to Johannesburg.