Sachverhalt: Sachverhalt: A. Das Landgericht Koblenz verurteilte den schweizerischen Staatsangehörigen W._ am 6. März 1990 wegen Mordes gemäss § 211 des deutschen Strafgesetzbuches zu lebenslanger Freiheitsstrafe. Diese Strafe verbüsste W._ zunächst im deutschen Vollzug. Auf sein Gesuch hin erfolgte im Juni 2000 die Überstellung zum Strafvollzug in der Schweiz. A. Das Landgericht Koblenz verurteilte den schweizerischen Staatsangehörigen W._ am 6. März 1990 wegen Mordes gemäss § 211 des deutschen Strafgesetzbuches zu lebenslanger Freiheitsstrafe. Diese Strafe verbüsste W._ zunächst im deutschen Vollzug. Auf sein Gesuch hin erfolgte im Juni 2000 die Überstellung zum Strafvollzug in der Schweiz. B. Mit Eingaben vom 25. Februar und 24. März 2003 stellte W._ ein Gesuch um bedingte Entlassung. Der Sonderdienst des kantonalen Justizvollzugs des Kantons Zürich lehnte das Gesuch am 8. Juli 2003 ab. Er bezog sich namentlich auf ein Gutachten vom 10. November 1999 sowie auf einen Bericht des Psychiatrisch-Psychologischen Diensts (PPD) des Kantons Zürich vom 14. Januar 2003 samt einer ergänzenden mündlichen Auskunft vom 2. Juli 2003. Der Gutachter hatte bei W._ eine paranoide Schizophrenie diagnostiziert und grundsätzlich eine ungünstige Prognose gestellt. Gemäss Bericht des PPD hat sich die Prognose seither nicht wesentlich geändert. Einen Rekurs gegen den Entscheid des Sonderdiensts wies die Direktion der Justiz und des Innern des Kantons Zürich am 18. November 2003 ab. Die dagegen erhobene Beschwerde von W._ wies das Verwaltungsgericht des Kantons Zürich am 22. April 2004 ab. Die dagegen erhobene Beschwerde von W._ wies das Verwaltungsgericht des Kantons Zürich am 22. April 2004 ab. C. W._ führt Verwaltungsgerichtsbeschwerde und beantragt, das angefochtene Urteil sei aufzuheben, und er sei bedingt zu entlassen. Eventuell sei die Sache zur Einholung eines psychiatrischen Gutachtens und zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Das Verwaltungsgericht begehrt die Abweisung der Beschwerde. 