Demostración de que existe un camino más corto entre dos nodos específicos en un dígrafo ponderado y conexo que no tiene ciclos negativos.

Question

Sea $G=(V,E,W)$ es un grafo dirigido, donde $V$ y $E$ son los conjuntos de nodos y aristas, respectivamente, mientras que $W: E \rightarrow \mathbb{R}$ es una función de peso arbitraria. Cómo demostrar que existe un camino más corto desde un $s \in V$ a un $t \in V$ sólo si $G$ no contiene ciclos de coste negativo. El camino más corto desde $s$ a $t$ es el camino $e_1,e_2,...,e_n$ para lo cual $\sum W(e_i)$ es mínima.

Estoy seguro de que se trata de una prueba muy elemental, pero no la he encontrado directamente.

Answer 1

Algunas reflexiones que pueden ser demasiado largas para un comentario: suponiendo que la longitud de un camino $e_1 \ldots e_n$ ser $W(e_1) + \cdots + W(e_n)$ Fijar $s,t \in V$ y considerar $\mathcal P$ el conjunto de (finito) y $\mathcal P_{s,t}$ el subconjunto de trayectorias de $s$ a $t$ . Tenemos una función de longitud

$$\ell \colon \mathcal P \to \Bbb R, \quad \ell(e_1\ldots e_n) = W(e_1) + \cdots + W(e_n)$$

que es compatible con la concatenación de caminos, es decir $\ell(\omega\omega') = \ell(\omega) + \ell(\omega')$ .

A más corto camino, por tanto, sería un camino $\omega \in \mathcal P_{s,t}$ que minimiza $\ell$ cuando se limita a $\mathcal P_{s,t}$ .

Si tenemos un ciclo $c$ conectado a ambos $s$ y $t$ a través de caminos $\omega_s,\omega_t$ entonces $\omega_s c^k \omega_t$ también es una ruta desde $s$ a $t$ que atraviesa $\omega_s$ y luego hace un bucle alrededor de $c$ para $k$ veces, y luego pasa por $\omega_t$ . Por cálculo directo,

$$\ell(\omega_s c^k \omega_t) = \ell(\omega_s) +k\ell(c)+\ell(\omega_s).$$

Por lo tanto, si el ciclo $c$ es negativa, por la fórmula anterior la función $\ell$ es arbitrariamente grande negativo valores en $\mathcal P_{s,t}$ y, por tanto, no puede alcanzar un valor mínimo.

Ahora, su tarea es demostrar lo contrario. Además, ten en cuenta que para que fuera un problema necesitábamos que el ciclo antes mencionado estuviera conectado a $s$ y $t$ . Si tenemos ciclos negativos en, digamos, una componente conexa disjunta de la de $s$ y $t$ no influye en el coste de los trayectos $s \to t$ .

Edita: Bien, algunos pensamientos más para el converso. Lo que se me ha ocurrido puede ser un poco engorroso, espero que alguien publique pronto una prueba inteligente. Pero de todos modos, aquí está mi intento:

Fijar $\omega$ un camino para $s$ a $t$ . Si $\omega = \omega' c \omega ''$ con $c$ a positivo (o más bien ciclo no negativo), entonces $\ell(\omega) \geq \ell(\omega' \omega'')$ . Así, para comprobar si $\ell$ alcanza un valor mínimo, podemos limitarnos a los caminos sin ciclos no negativos.

Pero entonces, por hipótesis, los caminos considerados tienen no ciclos. Si tu grafo es finito, hay una cantidad finita de vértices y por tanto sin hacer un ciclo hay opciones finitas para un camino desde $s$ a $t$ es decir, el subconjunto $S \subset \mathcal P_{s,t}$ de caminos acíclicos es finito. Por lo tanto $\ell$ alcanza un mínimo en $S$ y por la observación anterior se trata de un mínimo en $\mathcal P_{s,t}$ .