Sachverhalt: A. Das Bezirksgericht Zürich sprach X._ am 15. September 2015 des Raubs, des mehrfachen Diebstahls, des mehrfachen Fahrens ohne Berechtigung, der Entwendung eines Motorfahrzeugs zum Gebrauch, des mehrfachen Hausfriedensbruchs, der unrechtmässigen Aneignung, der üblen Nachrede sowie des geringfügigen Diebstahls schuldig. Es verurteilte ihn zu einer unbedingten Freiheitsstrafe von 16 Monaten unter Anrechnung des ausgestandenen Freiheitsentzugs von 267 Tagen sowie zu einer Busse von Fr. 300.--. X._ trat die Freiheitsstrafe am 15. September 2015 an. Das Strafende fiel auf den 21. April 2016. Am 5. November 2015 wurde X._ durch das Amt für Justizvollzug des Kantons Zürich per 10. November 2015 bedingt entlassen, nachdem er zwei Drittel der Strafe verbüsst hatte. Das Amt für Justizvollzug setzte die Probezeit auf ein Jahr fest und ordnete für deren Dauer Bewährungshilfe an. Die Direktion der Justiz und des Innern wies den von X._ eingereichten Rekurs am 16. Februar 2016 ab. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich am 20. Juni 2016 ab. B. X._ führt Beschwerde in Strafsachen. Er beantragt, das Urteil des Verwaltungsgerichts sei aufzuheben, und die Sache sei zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem ersucht er um Gewährung der unentgeltlichen Rechtspflege. C. Das Verwaltungsgericht des Kantons Zürich beantragt die Abweisung der Beschwerde, verzichtet aber auf eine Vernehmlassung zur Sache. Das Amt für Justizvollzug des Kantons Zürich verzichtet ebenfalls stillschweigend auf eine Vernehmlassung.