Wie bereits in einem Kommentar vermutet, ist die `\only`-Verteilung falsch. Mit dem Lesen der `\only`-Anweisung hat die jeweilige Zelle bereits begonnen.
\documentclass{beamer}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
\usepackage[T1]{fontenc}
\usepackage{amssymb}
\begin{document}
\begin{frame}
\only<1-2>{init mit Startknoten A\\}
\only<2->{Q = \{\only<2-3>{A,}\only<2-5>{B,}\only<2-9>{C,}\only<2-7>{D,}\only<2-11>{E}\}\\}
\only<3,5,7>{Wähle Knoten u aus Q mit kleinster Distanz \& distanz\_update\\[0,2cm]}
\only<2->{\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|}
\hline
u & \multicolumn{2}{c|}{A} & \multicolumn{2}{c|}{B} & \multicolumn{2}{c|}{C} & \multicolumn{2}{c|}{D} & \multicolumn{2}{c|}{E} \\
\hline
init & 0 & - & $\infty$ & - & $\infty$ & - & $\infty$ & - & $\infty$ & -
\only<4->{\\\hline A & & & 1 & A & 3 & A & 2 & A & 4 & A}
A}%
\only<6->{\\\hline B & & & & & 2 & B & 2 & A & &}
&}%
\only<8->{\\\hline D & & & & & & & & & 3 & D}
D}%
\only<10->{\\\hline C & & & & & & & & & 3 & D}
D}%
\only<12->{\\\hline E & & & & & & & & & & } }%
\\ \hline
\end{tabular}}
\end{frame}
\end{document}
So wird das `\only` hingegen am Ende der jeweils letzten Zelle einer Tabellenzeile gelesen und nur dann eine neue begonnen, wenn man sich bereits auf der richtigen Seite befindet.befindet.
Die ganzen `%` sind übrigens wichtig, damit keine zusätzlichen Leerzeichen entstehen, die sich dann natürlich auf die Spaltenbreite auswirken.
