Propiedades de la ruta más corta

El problema del camino más corto es el problema de encontrar un camino entre dos vértices (o Nodes) en un gráfico tal que la suma de los pesos de sus aristas constituyentes se minimice. El camino más corto entre dos Nodes cualquiera del gráfico se puede encontrar utilizando muchos algoritmos, como el algoritmo de Dijkstra , el algoritmo de Bellman-Ford , el algoritmo de Floyd Warshall . Hay algunas propiedades de encontrar las rutas más cortas en función de las cuales funciona el algoritmo para encontrar la ruta más corta:

1. Propiedad de subestructura óptima
   • Todos los subtrayectos del trayecto más corto también deben ser los trayectos más cortos.
   • Si existe la longitud de ruta más corta entre dos Nodes U y V , entonces elegir con avidez el borde con la longitud mínima entre V y S dará la longitud de ruta más corta entre U y S.
   • Todos los algoritmos enumerados anteriormente funcionan en función de esta propiedad.
   • Por ejemplo, sea P ₁ un subcamino desde (X → Y) del camino más corto (S →X →Y → V) del gráfico G . Y sea P ₂ cualquier otro camino (X → Y) en el gráfico G . Entonces, el costo de P ₁ debe ser menor o igual al costo de P ₂ . De lo contrario , el camino (S → X →Y → V) no será el camino más corto entre los Nodes S y V.
   

   Gráfica G

2. Desigualdad triangular
   • Sea d(a, b) la longitud del camino más corto de a a b en el gráfico G ₁ . Después,
     • d(a, b) ≤ d(a, x) + d(x, b)
   

   Gráfica G ₁