También podemos suponer que el gráfico $G$ está conectado. Sea $s$ sea el vértice inicial, $n$ sea el número de vértices y $m$ sea el número de aristas. En un primer momento hay que comprobar que la función $\pi\colon V\setminus \{\,s\,\} \to V$ de los padres en el árbol realmente produce un árbol, es decir, no hay una secuencia $v_1, \ldots, v_k$ de vértices que $v_1 = \pi(v_2)$ , $\ldots$ , $v_{k-1} \pi(v_k)$ y $v_k = \pi(v_1)$ . Es un árbol si y sólo si cada vértice puede ser alcanzado desde $s$ pasando de padres a hijos $\pi(v)$ al vértice $v$ solamente. Utilice un DFS de $s$ para comprobar la alcanzabilidad de todos los vértices, requiere $\mathrm O(m)$ tiempo.
Entonces debe comprobar para cada vértice $v$ que el para todos los vértices vecinos $u$ desigualdad $d(s, u) \ge d(s, v) + w_{uv}$ tiene ( $d(a, b)$ es la distancia entre vértices $a$ y $b$ y $w_{ab}$ es el peso de la arista $\{\,a, b\,\}$ ), es decir, para todos los vértices no se puede reducir la distancia. Se debe comprobar para cada egde una vez, por lo que requiere $\mathrm O(m)$ tiempo de nuevo.
Hay dos condiciones más: la distancia al vértice $s$ a sí mismo debe ser cero y la distancia a cualquier otro vértice $v$ debe ser igual a la distancia a su padre $\pi(v)$ más el peso del borde, conectándolos. La comprobación de la primera de estas condiciones requiere $\mathrm O(1)$ tiempo y la comprobación del segundo requiere $\mathrm O(n)$ tiempo. Todas las condiciones juntas: $$\begin{cases} \pi(\pi(\ldots\pi(v)\ldots)) = s & \forall v \in V(G) \,\\ d(s, u) \ge d(s, v) + w_{uv} & \forall u \in N_G(v),\\ d(s, s) = 0,\\ d(s, v) = d(s, \pi(v)) + w_{v\pi(v)} & \forall v \in V(G) \setminus \{\,s\,\}. \end{cases}$$ Necesitamos totalmente $\mathrm O(m)$ tiempo para el gráfico conectado $G$ . Si la necesidad de alguna condición o la suficiencia de sus agregados no son obvias, pregunte en los comentarios.
